Re: Congruence based factoring algorithm
- From: Tim Smith <reply_in_group@xxxxxxxxxxxxxxxx>
- Date: Sun, 30 Nov 2008 01:20:23 -0800
In article <jo33j4lu3art5l8diohvrgiv7sqqtlf766@xxxxxxx>,
rossum <rossum48@xxxxxxxxxxxx> wrote:
It would also be useful if you could qualify "near to" a bit more
accurately. How far away from sqrt(T) can p get? Obviously the
algorithm will run faster with as small a p as possible; what is the
lower limit on p? As Patricia says, is p = 3 allowed for all T?
Low primes work, in that they can give an ak such that ak = f1 mod p,
where f1 is a factor of nT. But to find the actual value of f1, you
need to check ak + jp, for j >= 0. You might have to try a lot of
values of j to find the right one, if p is small.
I think it ends up being a tradeoff. If you use large p, then you
essentially end up with a big search for suitable k, but once you find a
k that works, it isn't hard to find the factor. If you use a small p,
finding k is easy, but then you have a big search to go from the factor
mod p to the factor itself.
How about using multiple primes? That is, find an a1*k1 mod p1, a2*k2
mod p2, and so on, with the p's chosen so that p1*p2*... > nT. Use CRT
to figure out f1 mod p1*p2*....
(Pick all the p's so that the are 3 mod 4, so that computing the modular
square roots will be easy).
--
--Tim Smith
.
- Follow-Ups:
- Re: Congruence based factoring algorithm
- From: JSH
- Re: Congruence based factoring algorithm
- References:
- Re: Congruence based factoring algorithm
- From: rossum
- Re: Congruence based factoring algorithm
- Prev by Date: Re: Congruence based factoring algorithm
- Next by Date: Re: Congruence based factoring algorithm
- Previous by thread: Re: Congruence based factoring algorithm
- Next by thread: Re: Congruence based factoring algorithm
- Index(es):
Relevant Pages
|
