- Apr 7, 2013On 4/7/2013 7:33 AM, primenumbers@yahoogroups.com wrote:
>

Ok. You mean use a complex number as base instead of using a positive

> 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

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.

>

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 f

f 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

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.

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

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

On 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

because:

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 before

You 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 primes

Kermit

> Bernhard

>

>

>