Chemistry - Jones's period proxy algorithm

Jones's factoring-by-period-proxy algorithm is a number theoretic integer factorization algorithm, invented by R.C. Jones in 1964. It is a special-purpose algorithm, in that although it is valid for all composites of primes (except factors of the base), it is efficient for integers where the period of each factor is much smaller than the factor.

The algorithm is based on the insight that the inverse of prime numbers P (except 2 and 5, in base 10) always have a period r which is a factor of P − 1 and that P is always a factor of 10^r − 1.

It is a simple matter to see that the product of primes C with a period of r will be a factor of 10^r − 1.

Contents

1 Base concepts

2 Jones concepts

3 Interesting examples

4 Additional information

Base concepts

To find the period, first invert the number and then count how many places are in the repeating pattern. The period of 3 is 1, 7 is 6, 11 is 2.

When you multiply two or more primes, the periods combine similar to the lowest common denominator of the periods.

     Period of 3  = 1      Period of 11 = 2    Period of 37  = 3
     Period of 11 = 2      Period of 7  = 6    Period of 11  = 2
     Period of 33 = 2      Period of 77 = 6    Period of 407 = 6

Therefore the period of a composite number contains the "autographs" of its factors.

Jones concepts

By factoring the period of a composite as a proxy, the factors of the composite can be determined.

To factor a composite when the period of its primes are not equal:

Determine the period of the composite (We'll use xy). Count the number of digits in the repeating pattern. This is r_xy.

If xy = 77,  1/77 = 0.012987012987012987012987... then r_{xy = 6.}

10^rxy − 1 will have both x and y as factors.

3³ × 7 × 11 × 13 × 37 = 999999

Make a list of the divisors of r_xy.

 D6 = {3, 2, 1}

Do the following step once for each divisor until you get one of the factors.

    GCD ( 10^D6 − 1, xy )

or determine the greatest common divisor between

999 and xy = 1

99 and xy = 11

This does not work when the periods of x and y are equal because factoring the periods does not separate them.

So in the rare event that it did not work, simply change bases to one that is a coprime of the base you are working in. It is very unlikely that two primes would share the same period in more than one coprime base.

Interesting examples

501960895444186103939213477849572776695158277412120990847344708802451100161 = 59779577156334533866654838281 × 8396862596258693901610602298557167100076327481

In this example, Pxy = 7020

10^7020/2 − 1 yields a factor. This factorization took less than a second where as the elliptical curve method took two hours.

Similarly,

903211738419682152086062250136186726453016680272039415074931545506381748616888717838882409799570295360804141173033154598 548349945310801640648651848947299512964254179997082841386088553977281121149903191041635715138731679470519327982780854047 4832220258899339143079265425477325397282585084827474987213226048463560985550272617846119965440037377 factors in less than a second since Pxy = 512.

Although this number is larger than current RSA numbers, the ratio x/y puts it outside the range of being produced by RSA algorithms if they were extended to numbers of this size.

Additional information

Artin conjectured that Artin's constant C=0.3739558136... is the fraction of full reptend primes in base 10. This means that roughly 63 percent of primes have reduced reptends in base 10.

There is no current method for predicting which particular numbers have hyper-reduced reptends as in the examples above. Nor is there a method to determine the size of the hyper-reduced repend prime population.

It is unlikely that there are many numbers in the RSA crypto range that are susceptible to being efficiently factored using this method. But it is likely that there are at least a few.

The susceptible population is increased by the use of very large bases.

For instance, only 37 has a period of 3 in base 10.

In base 10⁴¹ − 1, there are eight numbers with a period of 3:

7, 13, 739, 51031, 148339, 16419517,

979796594227038466814289353530207129,

61051796035522969271171274876554178504544683763248923853725596423

If an efficient method were developed to obtain very large periods of composites, then a variation of the algorithm would be used which could be considered a general purpose algorithm:

1. Obtain the period.

2. Factor the period.

3. Develop a list of the combinations of the factors.

4. Add 1 to each member of the list. This list will contain the factors of the composite.

Challenges

1. Can the period be obtained for composites of full reptend primes in real time?

2. Is there a way to transform a prime into one of its period peers? For instance, from the example above, can 61051796035522969271171274876554178504544683763248923853725596423 be transformed into 7, 13, etc.? What is the property that makes these primes peers in a given base?

3. Is there a way to select a base that will cause a given composite to have a hyper-reduced period?

4. How can the population of hyper-reduced reptend primes be determined?

5. Are there other types of proxies useful for factoring?

Repeating Decimals

Any fraction m/n which is repeating in base 10 has a period $\lambda\;(n)$ which is independent of m. If n is relatively prime to 10 then $\lambda\;(n)$ is the multiplicative order of 10 (mod n). [1]

If n is relatively prime to 10 then $\lambda\;(n)$ is a divisor of $\phi\;(n)$ and has at most $\phi\;(n)$ digits, where $\phi\;$ is the totient function. If n is a prime and 10 is a primitive root of n, then $\lambda\;(n) = \phi\;(n)$

External Links

Several links to mathworld.wolfram.com about repeating decimals 1 2 3 4 5 6 7 8

Categories: Integer factorization algorithms