Re: A factoring algorithm
- From: "Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx>
- Date: 9 Jan 2006 06:05:54 -0800
hart_wb@xxxxxxxxx wrote:
> Hi,
>
> I have a new factoring algorithm which seems to be very fast with
> certain kinds of numbers.
>
> For example it will factor numbers which are the product of two primes
> which are both of the "same kind", and fairly close together (say are
> the same length to within 3 or 4 digits -though that isn't an absolute
> requirement if you do some fiddling and have a little more time), where
> by "same kind" I mean that they are both of the form:
>
> a*b^n+c where a, b and c are "small"
Your post lacks specifics. Define "small"
Is n fixed? You said in another post that b is fixed.
If, in fact, a and c are bounded by a polylog function of b^n Then
a factorization of N = (a1 x + c1)(a2 x + c2) where a_i, c_i <
log(x)^k for
some k, then this factorization is readily found in polynomial time
(where
x = b^n.)
Numbers of this form are also susceptible to the Special Number Field
Sieve.
It is *easy* to construct limited sub-sets of the integers, possessing
special
form whose factorizations are easy.
The world does not need another O(N^1/4) algorithm.
.
- Follow-Ups:
- Re: A factoring algorithm
- From: wbhart
- Re: A factoring algorithm
- From: wbhart
- Re: A factoring algorithm
- From: Phil Carmody
- Re: A factoring algorithm
- References:
- A factoring algorithm
- From: hart_wb
- A factoring algorithm
- Prev by Date: Re: RS-232 random number generator
- Next by Date: How to construct one-way permutation from one-way function?
- Previous by thread: Re: A factoring algorithm
- Next by thread: Re: A factoring algorithm
- Index(es):
Relevant Pages
|
