Integer Solutions In Modular Inverse Problems

by

Huen Y.K.

CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~huens/
http://web.singnet.com.sg/~activweb/
email: huens@mbox3.singnet.com.sg

(A short communication - Date released: 31/3/98)

Abstract

Modular inverse problems are based on finding integer solutions to the general equation 1 = (a*i) (mod j). Sometimes such a problem has solutions, sometimes not [1]. In this paper, the three parameters a, i, and j will be scanned for integer solutions with these parameters being identically and symmetrically bounded to take both positive and negative integer values. However j as the divisor must not take zero values. Computations are carried out in string-data mode rather than numerical mode using Macsyma 2.2.1 [3]. The objective is to determine the statistical distributions of integer solutions as the bounds +/- ub increase.


1. Introduction

The modular inverse problem is more difficult to solve analytically than the modular problem. Sometimes it has solutions and sometimes not. Integer solutions are found from 1 = (a*i) (mod n) with all three parameters identically and symmetrically bounded from -ub to +ub where ub is defined as the positive upperbound variable. Two mixed mode boolean functions BF1 and BF2 are defined, one being used to test for exact integer solutions whilst the second being used for testing relative primeness between a and j as given by equations (1a) and (1b) respectively.


Table 1 summarises the four category of solutions based on outputs of BF1 and BF2. Note that only Category (i) will yield the desired solutions.

Table 1 - Truth Table for 4 categories in modular inverses
..........................................BF1........................BF2
Category (i).......................True........................True
Category (ii)*....................True........................False
Category (iii).....................False.......................True
Category (iv).....................False.......................False

*Note: Category (ii) does not exist since it would imply that integer solutions to modular inverses can be found when parameters a and j are not relative prime.



2. String Divisions

Strictly string divisions do not exist in arithmetics. The ratio between two strings reverts to algebraic division where of course if the numerator and the denominator symbols are identical, the quotient will be a numeric unity value. Note that in both equations, numerical types are converted to string types and note that the division of one string by another will only yield a numeric value of unity if the two strings are identical. Thus both BF1 and BF2 will only return true if the strings are identical, otherwise false. These are confirmed in the worked example 1 below.



3. Numerical Scans

Computations are based on the Macsyma program line given by equation (2). The results are summarised in Table 2. To avoid divisions by zero, equation (2) has to be split into two expressions where j either takes the range 1 to ub or -ub to -1. Tag variables x and y are introduced to show that we can classify the solutions into four categories as shown in Table 1.

inverse_modulo:sum(sum(sum(f1(a,i,j)*x^oddp(string(1)/string((a*i-1)/j))*y^oddp (string(1)/string(gcd(a,j))),i,-ub,ub),a,-ub,ub),j,1,ub)+sum(sum(sum(f2(a,i,j)*x^oddp(string(1) /string((a*i-1)/j))*y^oddp(string(1)/string(gcd(a,j))),i,-ub,ub),a,-ub,ub),j,-ub,-1); ..................(2)

Table 2 - Distributions of solutions for ub from 2 to 20.
ub = 2;

Output (3a) gives the distributions of the four categories of solutions whilst output(3b) gives the solutions of individual terms. For brevity only the integer solutions are shown in equation (3b). The second output will not be shown in subsequent computations. f(a,i,j) associated with each term shows the values of indices used. All integer solutions are shown in bold fonts.

15 * x^true * y^true + 55 * x^false * y^true + 30 * x^false * y^false........(3a).

% integer solutions / total permutations = 15/125*100 = 12%

f1(2, 1, 1) * x^true * y^true + f2(2, 0, - 1) * x^true * y^true + f1(1, 2, 1) * x^true * y^true + f2(1, 0, - 1) * x^true * y^true + f2(1, - 1, - 2) * x^true * y^true + f2(0, 2, - 1) * x^true * y^true + f2(0, 1, - 1) * x^true * y^true + f2(0, 0, - 1) * x^true * y^true + f2(0, - 1, - 1) * x^true * y^true + f2(0, - 2, - 1) * x^true * y^true + f2( - 1, 1, - 2) * x^true * y^true + f2( - 1, 0, - 1) * x^true * y^true + f1( - 1, - 2, 1) * x^true * y^true + f2( - 2, 0, - 1) * x^true * y^true + f1( - 2, - 1, 1) * x^true * y^true + ...........................................(3b).

ub = 3:
29 * x^true * y^true + 181 * x^false * y^true + 84 * x^false * y^false
% integer solutions / total permutations = 29/343*100 = 8.45%
ub = 4:
41 * x^true * y^true + 373 * x^false * y^true + 234 * x^false * y^false
% integer solutions / total permutations = 41/729*100 = 5.62%
ub = 5:
59 * x^true * y^true + 799 * x^false * y^true + 352 * x^false * y^false
% integer solutions / total permutations = 59/1331*100 = 4.43%
ub = 6:
71 * x^true * y^true + 1151 * x^false * y^true + 806 * x^false * y^false
% integer solutions / total permutations = 71/*2197 = 3.23%
ub = 7:
91 * x^true * y^true + 2039 * x^false * y^true + 1020 * x^false * y^false
% integer solutions / total permutations = 91/3375*100 = 2.70%
ub = 8:
105 * x^true * y^true + 2853 * x^false * y^true + 1666 * x^false * y^false
% integer solutions / total permutations = 105/4913*100 = 2.14%
ub = 9:
125 * x^true * y^true + 4093 * x^false * y^true + 2280 * x^false * y^false
% integer solutions / total permutations = 125/6859*100 = 1.82%
ub = 10:
139 * x^true * y^true + 5195 * x^false * y^true + 3486 * x^false * y^false
% integer solutions / total permutations = 139/9261*100 = 1.50%
ub = 11:
163 * x^true * y^true + 7519 * x^false * y^true + 3956 * x^false * y^false
% integer solutions / total permutations = 163/12167*100 = 1.34%
ub = 12:
175 * x^true * y^true + 8975 * x^false * y^true + 5850 * x^false * y^false
% integer solutions / total permutations = 175/15625*100 = 1.12%
ub = 13:
199 * x^true * y^true + 12275 * x^false * y^true + 6480 * x^false * y^false
% integer solutions / total permutations = 199/19683*100 = 1.01%
ub = 14:
215 * x^true * y^true + 14575 * x^false * y^true + 8758 * x^false * y^false
% integer solutions / total permutations = 215/24389*100 = 0.88%
ub = 15:
237 * x^true * y^true + 17557 * x^false * y^true + 11036 * x^false * y^false
% integer solutions / total permutations = 237/29791*100 = 0.80%
ub = 16:
253 * x^true * y^true + 20801 * x^false * y^true + 13794 * x^false * y^false
% integer solutions / total permutations = 253/35937*100 = 0.70%
ub = 17:
279 * x^true * y^true + 26531 * x^false * y^true + 14840 * x^false * y^false
% integer solutions / total permutations = 279/42875*100 = 0.65%
ub = 18:
291 * x^true * y^true + 29827 * x^false * y^true + 19166 * x^false * y^false
% integer solutions / total permutations = 291/50653*100 = 0.57%
ub = 19:
319 * x^true * y^true + 37043 * x^false * y^true + 20436 * x^false * y^false
% integer solutions / total permutations = 319/59319*100 = 0.54%
ub = 20:
335 * x^true * y^true + 41567 * x^false * y^true + 25338 * x^false * y^false
% integer solutions / total permutations = 335/68921*100 = 0.49%
ub = 40:
775 * x^true * y^true + 316583 * x^false * y^true + 207522 * x^false * y^false
% integer solutions / total permutations = 775/531441*100 = 0.146%

The rapid fall in percentage integer solutions is to be expect in view of the fact that the number of permutations increases proportionally to (2*ub+1)^3 whereas the increase in the number of integer solutions is nearer to ub.

4. General formulation for modular inverse function

Some number theoretic problems remained unsolved probably because conventional algebra and boolean algebra do not possess sufficient expressivity to solve them in the first place. Every mathematical system is incomplete in some ways and when it hits its limits, it becomes rather awkward as an analytical tool. Using mixed mode formulations in sequence algebra, the author successfully developed the global formulation for the twinprime sequence [8]. Most recently, using the same tool, he revealed that pie can be predicted from the summation of periodic sequences [9]. Such breakthroughs were only possible because mixed mode formulations possess higher expressivity than conventional algebraic formulations. Perhaps a new name should be coined for this new type of algebra called algorithmic algebra since it is neither fully analytical nor fully numerical. This type of algebra has its niche because it addresses the lack of expressivity of conventional algebra.

In this section, the development of a general modular inverse function is described. This function complies with the defintion of a mathematical function but it does not give explicit analytical solutions. Two new algebraic constructs are admitted into mixed mode functions, viz., the use of MMFs and the use of iterative loops.

Expressivity in sequence algebra is enhanced by the synergistic use of mixed mode functions, i.e., expressions which include both arithmetic and boolean operations. Using this, it is possible to develop an algebraic formulation for modular inverses as shown in equation (3). Note that this equation makes use of MMFs instead of just boolean functions. At the end of the computations, the output will be purely numeric. Note that in order to avoid zero divisors, the RHS contains two independent expressions one of which covers the positive range of ub whilst the other the negative range being toggled by the switch variables n1 and n2 respectively.

F(a, ui, uj, n1, n2) :=

.......-1........ui........uj
.......==== ==== ====
........\........\.........\......................................string(1)
n1*( >........>.......>.........f(a, i, j) (oddp(---------------) - false) *
....... /......../........./............................................i*a - 1
.......==== ==== ====.........................string(-------)
.......j=-uj...i=ui...a=-uj..........................................j

....................................................string(1)..........................................2
....................................(oddp(-----------------) - false))/(true - false)
................................................string(gcd(a, j))

.............uj.......ui......uj
...........==== ==== ====
............\ ........\.........\....................................string(1)
+n2*(...>.......>........>.....f(a, i, j) (oddp(---------------) - false) *
.........../........./........./........................................i*a - 1
..........==== ==== ====......................string(-------)
............j=1.....i=ui....a=-uj.....................................j

...................................................string(1)..........................................2
...................................(oddp(-----------------) - false))/(true - false).........(3).
..............................................string(gcd(a, j))

For example if (1/a) = i (mod j) = 5 (mod 14) then the integer solution is 3 and there is no solution to 2 (mod 14). To solve a specific modular inverse problem, one must input known values of ui, uj, n1, and n2 and the function will return the integer solution if there it exists or zero if it does not exist. The Macsyma program line for the above equation by equation (4). It is obviously more intuitive to read equation (3) than equation (4).

inverse_modulo(a,ub1,ub2,n1,n2):=n1*sum(sum(sum(f1(a,i,j)*(oddp(string (1)/string((a*i-1)/j))-false)*(oddp(string(1)/string(gcd(a,j)))-false)/(true-false)^2,a,1,ub2 ),i,ub1,ub1),j,ub2,ub2)+n2*sum(sum(sum(f2(a,i,j)*(oddp(string(1)/string((a*i-1)/j))-false) *(oddp(string(1)/string(gcd(a,j)))-false)/(true-false)^2,a,-ub2,-1),i,ub1,ub1),j,-ub2,-ub2)$ ..................................(4).

In equation (4), integer solution of a is to be found, where ub1 = i, ub2 = j, n1 = 1 will toggle on the positive range of j, and n2 = 1 the negative range of j. Thus n1 = n2 = 1 will toggle on both positive and negative range of j. Given below are some sample solutions.

inverse_modulo(a,5,14,1,0);
f1(3, 5, 14)

inverse_modulo(a,5,14,0,1);
0

inverse_modulo(a,5,14,1,1);
f1(3, 5, 14)

inverse_modulo(a,2,14,1,1);
0

5. Conclusions

This paper describes a Macsyma program which can be used to scan integer solutions of modular inverse problems. A novel feature in this program is the use of string divisions which is only viable if the numerator and the demoninator strings are identical. This program performs correctly because the two predicate functions test for identical strings as a numerical unity value. The rapid fall in percentage of integer solutions over total permutations is within expectations. Nevertheless, it shows that if large values of ub are used, the occurrences of integer solutions are very small and are hard to find since analytical prediction methods are not available.

In section 4, the author proposed a formulation for the solutions of modular inverses which has all the trappings of an algebraic function. This function is found to work correctly although it does not give analytical solutions to modular inverses. The author suggests that algebra involving mixed mode functions should be called algorithmic algebra since a whole computer program can be represented by a standalone algebraic formulation. This is possible if we use mixed-mode functions. It suggests that it is now possible to develop a computer algorithm as an algebraic formulation before converting it into a software program. One advantage of this approach is that the number of do loops can be greatly reduced being replaced by MMFs which are very modular and modifiable.

Modular inverse problems are of interest to cryptographers. A previous paper in sequence algebra shows a unified view of the three major families of cryptographic systems, viz., one-time pad, public-key systems, and symmetric key systems [2]. The author thinks that sequence algebra should be able to find a niche in cryptographic developments in view of its strength in number theoretic problems [4 to 11].

6 References

The first three papers are directly relevant to the present paper. The remaining papers may be useful to those who are not familiar with sequence algebra.

1. Schneier Bruce:Applied Cryptography, Protocols, Algorithms, and Source Code In C, Second Edition, Wiley, pp 29-30.

2. Unified Classifications Of Keyed Cryptographic Algorithms - Huen Y.K. (Date Released 23/3/98, 22 Kbytes)

================================================
3. Macsyma: Symbolic/numeric/graphical mathematics software, Mathematics and System Reference Manual, 16th edition, relevant sections.

4. Sequence Algebra - A Tutorial Paper - Huen Y.K. (Date Released 2/2/98, 46 Kbytes)

Published Papers:

5. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci. Technol., 1994, VOL. 25, NO.6, pp 913-920.

6. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ. Sci. Technol., 1996, VOL.27, NO. 5, 685-691.

7. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol., 1997, VOL.28, NO.3, pp 333-344.

8. Huen Y.K.: The twin prime problem revisited, INT. J. Math. Educ. Sci. Technol.,1997, VOL.28, NO. 6, pp 825-834.

9. Huen Y.K.: Is Pie Periodic?, INT. J. Math. Educ. Sci. Technol.,1998,VOL.29,NO.1,19-26. (in the press).

10. Huen Y.K.: Final value theorem in number sequences., INT. J. Math. Educ. Sci. Technol.,199?,VOL.-??,NO.?,???-???. (accepted).

Papers posted in this website.

Comments: References from this point onward are not referred in the main paper. Most are provided for readers not familiar with sequence algebra. These papers can be easily hyperlinked whilst you surf into this URLsite.

11. A Simple Introduction To Sequence Algebra - by Huen Y.K. (date release: 15.3.97) (38 KBytes, 11*A4 pages).

===============END OF PAPER ============