Re: [PrimeNumbers] Digest Number 3672
- On 4/7/2013 7:33 AM, email@example.com wrote:
>Ok. You mean use a complex number as base instead of using a positive
> 1. A proposition for a better factorisation algorithm
> Posted by: "bhelmes_1" bhelmes@... bhelmes_1
> Date: Sat Apr 6, 2013 9:15 am ((PDT))
> A beautiful day,
> a very brief proposition for a better factorisation algorithm,
> based on the basic ideas of Pollard p-1 algorithm
> 1. Instead of using N, take C
number as base.
> a) Instead of an exponentation by primes, use only an exponentation by NOk. You mean that your exponents will be general positive integers
instead of being limited to primes.
>ok. You mean that the complex number you start with must not have
> b) Choose natural numbers a(1) and b(1) not equal 0 for the start point
either part equal to zero. It is not a pure imaginary,
or a pure real number. You do need to specify that the starting complex
number is a complex integer.
> c) Calculate a(n+1)+b(n+1)=(a(n)+b(n)I)^exponent mod ff is the positive composite integer to be factored.
> where f is the composite number
Here you mean that you are creating a sequence of exponentiations.
Your starting complex number is a0 + b0 I
a1 + b1 I is (a0 + b0 I)^e1
a2 + b2 I is (a1 + b1 I)^e2
Also, please tell us how the exponent sequence, e1, e2, e3, ...
> d) calculate res=gcd (a(n+1), f) and res=gcd (b(n+1), f) not every time, but after 1000 exponentation for example.No, this is not the best re-calculation.
> res gives the searched factor of f
> e) You can store the value af a(1000*k) and b(1000*k)
> if b(1000*(k+1))=0 you can recalculate the sequence
> and make each time a gcd by every exponentation
What you need to do is:
Suppose z0 is your starting complex number.
All calculations are in mod f.
z1 is z0^e1
z2 is z1^e2
z3 is z2^e3
Then as you calculate the z's you also calculate the product of the z's
w0 = 1
z1 = z0^e1
w1 = w0 * (z1 - 1)
z2 = z1^e2
w2 = w1 * (z2 - 1)
z3 = z2^e3
w3 = w2 * (z3 - 1)
when w_k goes to zero,
then apply GCD to w_(k-1).
Otherwise take every 100 or 1000 or some other prechosen interval to
apply the GCD. Which interval you choose will depend on the expected
difficulty of the factoring.
It would not be wise to choose an interval of 1000 if you expect the factor
to be found in less than 100 iterations.
> For the second part of Pollard p-1 you could use a lattice instead of searching linear which can be done on a clusterOn the average it would not matter whether you chose quadratic residue
> 2. Instead of using N, use the field of adjoined square
> a+b*sqrt (A) where A is a non quadratic residuum mod f
or non quadratic residue
Suppose f = x y where x and y are prime.
If you want a quadratic non-residue, you would want the quadratic
non-residue to be with respect to x or y.
Since you do not yet know x are y, it is not possible to chose a
quadratic non-residue for them.
If you chose a non-quadratic residue with respect to f,
then it would be a quadratic residue with respect to one of x,y
and a quadratic non-residue with respect to the other factor.
> same algorithm as beforeYou could do your steps 2 and 3 is parallel.
> 3. Instead of using N, use the field of complex adjoined square
> a+b*sqrt(A)I where A is a non quadratic residuum mod f
> same algorithm as before
> You can execute 1.,2. and 3. parallel.
The standard second part of the (p-1) algorithm cannot be started until
the first part is completed.
> Nice greetings from the primesKermit