Simple integer factorization algorithm

I've found that you can solve directly for f_1 and f_2 when f_1*f_2 =
T, where T is a composite to be factored.

With all positive integers:

f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p

and 'a' is related to k mod p by

a^2 = (T)(k^2)^{-1} - 1 mod p

where p is what I call a helper prime.

Notice that because f_1 = ak mod p, ak must be greater than p, if f_1
is less than p, if k is coprime to T.

Note that a^{-1} mod p is the modular inverse mod p, as is (k^2)^{-1}
mod p.

To get the direct solution you pick p a prime where p>sqrt(T) and pick
for k a positive integer near p, coprime to p, if you accidentally
have a factor in common with T then you have factored it, which I
mention only because in programming the algorithm you need to check
for that case.

You then find if 'a' exists for your k and if it does you check if ak
is greater than p, if it is, then you solve for f_1, if not you
decrement k, and try again. There is a 50% chance of success for each
k that 'a' exists.

Example: Let T=119. Then p=11 is greater than sqrt(119), and trying
k=10 gives

a^2 = (119)(10^2)^{-1} - 1 mod 11 = 8 mod 11,

but 8 is not a quadratic residue modulo 11, so no 'a' exists for this
case. Trying now k=9, gives

a^2 = (119)(9^2)^{-1} - 1 mod 11 = 4 mod 11

so a=2 is a solution. And ak = 18, which is greater than 11, so

f_1 = ak = 18 mod 11 = 7 mod 11.

And you have a non-trivial factorization, as 7 is a factor of 119.

The algorithm you'll note is polynomial time and uses residues when
conventional wisdom was that you couldn't solve for integer factors
with residues, but the key here appears to be quadratic residues,
where you get an interlocking mechanism.


James Harris
.

Relevant Pages

  • Re: JSH: Now were golden!
    ... which the negative of the quadratic residue is a quadratic residue and ... but some primes exclude themselves but only if ... factorization, but then again it might not. ... an 'a' for every unique factorization, ...
    (sci.crypt)
  • Re: JSH: Now were golden!
    ... which the negative of the quadratic residue is a quadratic residue and ... but some primes exclude themselves but only if ... they are the primes for which the negative of their quadratic residue ... factorization, but then again it might not. ...
    (sci.crypt)
  • Re: JSH: Now were golden!
    ... which the negative of the quadratic residue is a quadratic residue and ... but some primes exclude themselves but only if ... they are the primes for which the negative of their quadratic residue ... factorization, but then again it might not. ...
    (sci.crypt)
  • Re: Diophantine equation
    ... fact that N should be a multiple of 3 can be easily proved. ... Evidently -1 must be a quadratic residue mod d. ... I would hazard a guess that this is sufficient for there to be a solution. ...
    (sci.math)
  • Goldbachs conjecture and quadratic residues
    ... but it looks like the math establishment is still going to try ... quadratic residue, or it must have r mod p_1 as a quadratic residue. ... This results relates the sum of primes p_1 and p_2 to the factorization ...
    (sci.crypt)