mersenneforum.org > Math a primesieve of the kind f=1 or f=7 mod 8 with the function f(u,v)=u²+2uv-v²
 Register FAQ Search Today's Posts Mark Forums Read

 2018-03-23, 23:54 #1 bhelmes     Mar 2016 52·11 Posts a primesieve of the kind f=1 or f=7 mod 8 with the function f(u,v)=u²+2uv-v² 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
2018-03-24, 00:22   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 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 ?

 2018-03-24, 00:54 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23A816 Posts Can you explain what the word 'mersenne' is doing in the title? Click-bait much?
2018-03-24, 01:16   #4
bhelmes

Mar 2016

1000100112 Posts

Quote:
 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

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

2018-03-24, 02:04   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 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.

2018-03-24, 02:39   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts

Quote:
 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.

2018-03-24, 07:38   #7
bhelmes

Mar 2016

52·11 Posts

Quote:
 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

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

 2018-03-24, 13:26 #8 science_man_88     "Forget I exist" Jul 2009 Dumbassville 8,369 Posts 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.
 2018-03-24, 14:11 #9 Dr Sardonicus     Feb 2017 Nowhere 67768 Posts 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. Last fiddled with by Dr Sardonicus on 2018-03-24 at 14:14
 2018-03-25, 11:13 #10 bhelmes     Mar 2016 52×11 Posts 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
 2018-04-16, 23:54 #11 bhelmes     Mar 2016 52·11 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 28 2018-02-11 00:28 bhelmes Miscellaneous Math 9 2017-11-17 21:09 a1call Miscellaneous Math 3 2017-06-29 11:15 schickel Forum Feedback 18 2011-01-22 20:29 davar55 Puzzles 7 2007-09-21 11:24

All times are UTC. The time now is 23:48.

Thu Oct 29 23:48:02 UTC 2020 up 49 days, 20:59, 1 user, load averages: 1.94, 2.10, 2.02