a primesieve of the kind f=1 or f=7 mod 8 with the function f(u,v)=u²+2uv-v²

[bhelmes]

A peaceful night for all,

there is a description and a first basic implementation for a primesieve concerning the primes p=1 and p=7 mod 8.

http://devalco.de/poly_xx+2xy-yy.php

There are some improvements possible and i will try to give some improvements in some days.

Is an implementation with cuda possible ?
I need only a gcd for 128 bit values.

Greetings from the biquadratic functions
Bernhard

[science_man_88]

Originally Posted by bhelmes

A peaceful night for all,

there is a description and a first basic implementation for a primesieve concerning the primes p=1 and p=7 mod 8.

http://devalco.de/poly_xx+2xy-yy.php

There are some improvements possible and i will try to give some improvements in some days.

Is an implementation with cuda possible ?
I need only a gcd for 128 bit values.

Greetings from the biquadratic functions
Bernhard

So euc!idean gcd won't work ? Binary gcd ? Etc ?

[Batalov]

Can you explain what the word 'mersenne' is doing in the title?
Click-bait much?

[bhelmes]

Originally Posted by Batalov

Can you explain what the word 'mersenne' is doing in the title?
Click-bait much?

the factors of mersenne numbers f are all of the kind f=1 or f=7 mod 8

in contrast to the function f(u,v)=u²+v² which sieves p=1 mod 4
the function f(u,v)=u²+2uv-v² sieves p=1 and p=7 mod 8

By the way, there was a thread about primesieving with f(u)=2u²-1
the sieving algorithm with the biquadrat solves the problem with the needed ram and can be segmented as far as i can see.

Greetings from the primes
Bernhard

P.S. i have tried to give an exact title for the thread

[science_man_88]

Originally Posted by bhelmes

the factors of mersenne numbers f are all of the kind f=1 or f=7 mod 8

And of specific form.

[Batalov]

Originally Posted by bhelmes

the factors of mersenne numbers f are all of the kind f=1 or f=7 mod 8

Fail!

So what that they are "of the kind f=1 or f=7 mod 8"?!

For p=1000003, the factors of Mersenne_p are a subset of { 2*1000003+1, 4*1000003+1, 6*1000003+1,...}, that is you only need to try less than one in two million, but you are suggesting to sieve with every "f=1 or f=7 mod 8" that is one in every two primes?

Click-bait, just like we suspected.

[bhelmes]

Originally Posted by Batalov

Fail!

A peaceful and pleasant morning for you, Batalov

You did not understand the beauty of the algorithm

I did not suggest to use every prime of the sieve for one mersenne number.
I thought more to use the primes for a "couple" of mersenne numbers
and using the condition of the factors of mersenne numbers as science_man_88 pointed to.

Is there a difference between linear sieving and quadratic sieving
concerning the probality to find a factor ?

By the way, the topic is a bit older
http://www.mersenneforum.org/showthread.php?t=20564

And thank you that you did not throw this thread immeadiatley in Math.misc

I recommand for you a good breakfast
with a delicious coffee and some fresh croissants
in order to get a good start in the day.
Bernhard

[science_man_88]

Gcd of u and v is 1.
u and v are opposite parity.
For any prime exponent p, unless (p+1)/2 is a quadratic residue u and v can't be same value mod p.

[Dr Sardonicus]

Of course, it is well known that if p is an odd prime, q is prime, and q divides 2^p - 1, then q is congruent to 1 (mod 2*p). To incorporate the requirement that q be congruent to 1 or 7 (mod 8), requires only an exercise in elementary linear congruences. This requirement eliminates half the values of k from consideration.

There are two cases: p == 1 (mod 4), and p == 3 (mod 4).

Case 1: p == 1 (mod 4).

If 2*k*p + 1 == 1 (mod 8) we have

2*k*p == 0 (mod 8). Dividing through by 2 -- all the way through, including the modulus, we obtain

k*p == 0 (mod 4). Since p == 1 (mod 4) we have

k == 0 (mod 4).

Similarly, if p == 1 (mod 4) and 2*k*p + 1 == 7 (mod 8) we obtain

k == 3 (mod 4).

So: p == 1 (mod 4) ==> k == 0, 3 (mod 4).

In exactly the same manner we find in

Case 2: p == 3 (mod 4)

that p == 3 (mod 4) ==> k == 0, 1 (mod 4).

Of course, there is no guarantee that q = 2*k*p + 1 is prime; but one can do some sieving to exclude cheaply a lot of cases where q isn't prime, by dint of having small prime factors.

If it happens that p = 4*r + 3 and q = 8*r + 7 are both prime (Sophie Germain primes), then q is automatically a factor of 2^p - 1.

[bhelmes]

A peaceful sunday for all,

i have added a segmented version of the primegenerator.

The algorithm is therefore not limited by used ram,
which was a problem sooner.

http://devalco.de/poly_xx+2xy-yy.php#4

For a mersenne presieve i thought, that the possible candidates are calculated, follow by the sieving and checking m%f by fast exponentatiton.
(m should be the mersenne number and f the possible factor)

By the way, this implementation is one solution of the previous thread
http://www.mersenneforum.org/showthread.php?t=22693

Greetings from the complex plane
Bernhard

[bhelmes]

A peaceful night for everyone,

if i have two equations :
u²-v²+2uv = 0 mod f and
r²-s²+2rs = 0 mod f (u,v,r,s element N, u<>r, v<>s, f=a*b)

can i calculate a factor of f ?

Example:
16²-15²+2*16*15 = 0 mod 511
20²-3² + 2*20*3 = 0 mod 511

Greetings from the metrics
Bernhard