## 25026Re: [PrimeNumbers] Digest Number 3672

Expand Messages
• Apr 7, 2013
On 4/7/2013 7:33 AM, primenumbers@yahoogroups.com wrote:
>
> Message
> ________________________________________________________________________
> 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

Ok. You mean use a complex number as base instead of using a positive
number as base.
> a) Instead of an exponentation by primes, use only an exponentation by N

Ok. You mean that your exponents will be general positive integers
instead of being limited to primes.

>
> b) Choose natural numbers a(1) and b(1) not equal 0 for the start point

ok. You mean that the complex number you start with must not have
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 f
> where f is the composite number

f is the positive composite integer to be factored.

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

etc

Also, please tell us how the exponent sequence, e1, e2, e3, ...
is determined.

> d) calculate res=gcd (a(n+1), f) and res=gcd (b(n+1), f) not every time, but after 1000 exponentation for example.
>
> 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

No, this is not the best re-calculation.

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
etc

Then as you calculate the z's you also calculate the product of the z's
mod f.

w0 = 1
z1 = z0^e1
w1 = w0 * (z1 - 1)

z2 = z1^e2
w2 = w1 * (z2 - 1)

z3 = z2^e3
w3 = w2 * (z3 - 1)

etc

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 cluster
>
> 2. Instead of using N, use the field of adjoined square
> a+b*sqrt (A) where A is a non quadratic residuum mod f

On the average it would not matter whether you chose quadratic residue
because:

Suppose f = x y where x and y are prime.

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

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 before
>
> 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.

You could do your steps 2 and 3 is parallel.

The standard second part of the (p-1) algorithm cannot be started until
the first part is completed.

> Nice greetings from the primes
> Bernhard
>
>
>

Kermit