ALGEBRAIC FACTORING OF THE CRYPTOGRAPHY MODULUS AND PROOF OF GOLDBACH'S CONJECTURE

James Constant

[email protected]

Solving an Algebraic Quadratic Equation Factors the Cryptographic Modulus p=ab of Prime Numbers a and b and Proves Goldbach's Conjecture

Introduction

In the RSA cryptographic system a user chooses a pair of prime numbers a and b so large that factoring the product (modulus) p=ab is beyond all projected computing capabilities. As of 1984, the consensus was that a and b need to be about 75 decimal digits in size, and so p was roughly a 150-digit number. Since the largest hard numbers that could then be factored were 80 digits or less in size, and since the difficulty of factoring grows exponentially with the size of the number, 150 digits appeared cryptosecure for the foreseeable future.1 In 1996, a 130 digit number was factored and cryptographers talked about 100 digit prime numbers and 200 digit moduli.2 Today, some suggest 1024 and 2048 digit moduli.3

Goldbach's conjecture (GC) suggests that every even number greater than 2 is the sum s of two prime numbers a and b, i.e., a + b = s where s is even >2. Up to now, no one has been able to prove the GC.4 In the present paper, first, I assume that GC is correct and show that this assumption leads to an easy algebraic solution which factors the cryptographic product p=ab and, second, reversing my argument, I prove GC.

Algebraic Factoring of the Cryptographic Modulus

Consider the product p and sum s of two prime numbers a and b

(1) .....ab=p ............... p known, a and b unknown

..........a + b = s ........GC s even >2.

from which a and b are to be found. Equations (1) lead to the algebraic quadratic equation

(2) ....a2 - sa + p = 0

whose solution is

(3)...

and, since a is a prime number, I deduce, first, that is an even number, second, since s is an even number >2, c is an even number and, third, s. The two values given by (3) correspond to the two possible sets a,b or b,a (since ab=ba=p).

Since both s2 and c2 are even numbers, and since 4p is a known number, I can find

(4) ....s2 = c2 +4p

simply by adding even numbers c2 (c even) to 4p until the sum reaches s2, as required by (4).

For example, let p=55, the product of (unknown) primes a=5 and b=11. In this case s2>4p=220 so that candidate solutions are s2=16 2=256,182=324, 202=400, etc. And the corresponding c2=s2 - 220 are 36,104,180, etc. of which only the first is the square of an even number c, as required by (3). Accordingly, s=16 and c=6 which when substituted in (3) provide values for the primes a=5 and b=11.

Number of Operations Involved in Finding a and b

1. Given the product p of two unknown primes a and b start by computing 4p

2. Find the first candidate solution s

3. compute c2 =s2 - 4p for the first candidate solution s2

4. determine if the computed c2 for the first candidate solution s2 is the square of an even number c, as required by (3). If not reject and repeat steps 2-4 for the second candidate solution s2

5. Compute the sum and difference and divide by 2, as required by (3).

All in all, step 1 requires a product 4p; step 2 requires a squaring and equality or inequality operations to obtain s2; step 3 requires a subtraction to obtain c2; step 4 requires a square root to obtain and identify c as an even number; and step 5 requires a sum and difference each divided by 2.

By way of comparison with the RSA algorithm, encrypt KE and decrypt KD keys are easily obtained by knowing primes a and b. If one does not know a and b it has been as difficult to find the decrypt key KD as it is to factor modulus p=ab, by conventional methods, and this is the basis for the cryptosecurity of the RSA algorithm. In short, the RSA algorithm rests on its key method which is simpler to perform than is conventional factoring. Yet, one who has ciphertext C and knows decrypt key KD must perform operation , i.e., raise ciphertext C to the KD power and divide by modulus p to obtain plaintext P. Since products p have several thousand digits, the required operations of the Algebraic Solution are less difficult than those for the RSA algorithm.

Proof of Goldbach's Conjecture

Start from equation (2) in which a,s,p are integers. If I specify s is any even number greater than 2 and p is a product of two primes a and b, equation (2) devolves into s = a + b proving GC. The actual values of a and b are provided by equation (3). Proof of GC also proves the Twin Primes conjecture.5

CONCLUSIONS

The Algebraic Solution (3) of quadratic equation (2) factors the cryptographic modulus p=ab with a few simple algebraic operations, a distinct advantage over present key and factoring methods.6 It can be implemented for any size cryptographic modulus thus forcing cryptographers to go to even higher cryptographic primes and consequently slowing down cryptographic machines making them unusable. Quadratic equation (2) and its solution (3) provide a proof of GC.

1 See Cryptography at http://britannica.com/bcom/eb/article/3/0,5716,117763+7+109639,html?query=rsa%...

2 See Why do cryptography experts get excited about prime numbers? at http://www.madsci.org/posts/archives/may98/893442660.Cs.r.html

3 SeeThe Mathematical Guts of RSA Encryption at http://world.std.com/~franl/crypto/rsa-guts.html

See The New RSA Factoring Challenge at http://www.rsasecurity.com/rsalabs/challenges/factoring

4 See Goldbach's Conjecture at http://primes.utm.edu/glossary/page.php?sort=GoldbachConjecture

5 See Proof of the Twin Primes Conjecture at http://tprimes.coolissues.com/tprimes.htm

6 See Cryptographic Algorithms at http://www.ssh.fi/tech/crypto/algorithms.html

Copyright 2002 by James Constant

By same author: http://www.coolissues.com/mathematics/sameauthor.htm