Re: Simple integer factorization algorithm
- From: JSH <jstevh@xxxxxxxxx>
- Date: Sun, 30 Nov 2008 08:15:23 -0800 (PST)
On Nov 28, 3:13 pm, JSH <jst...@xxxxxxxxx> wrote:
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, <deleted>
It has been pointed out to me that the equation show that
nT - k^2 = f_1^2 mod p
so picking k directly is equivalent to guessing at the quadratic
residue mod p of one of the factors.
I should have noticed that before but didn't until a poster pointed it
out.
James Harris
.
- References:
- Simple integer factorization algorithm
- From: JSH
- Simple integer factorization algorithm
- Prev by Date: Re: Oddity with java.util.SortedMap
- Next by Date: Re: Oddity with java.util.SortedMap
- Previous by thread: Re: Simple integer factorization algorithm
- Next by thread: wholesale ugg5815 5825 5325 boot www.honestaaa.com
- Index(es):
Relevant Pages
|
