20180323, 23:54  #1 
Mar 2016
5^{2}·11 Posts 
a primesieve of the kind f=1 or f=7 mod 8 with the function f(u,v)=u²+2uvv²
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+2xyyy.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 
20180324, 00:22  #2  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:


20180324, 00:54  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23A8_{16} Posts 
Can you explain what the word 'mersenne' is doing in the title?
Clickbait much? 
20180324, 01:16  #4  
Mar 2016
100010011_{2} Posts 
Quote:
in contrast to the function f(u,v)=u²+v² which sieves p=1 mod 4 the function f(u,v)=u²+2uvv² 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 

20180324, 02:04  #5 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 

20180324, 02:39  #6  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 
Quote:
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? Clickbait, just like we suspected. 

20180324, 07:38  #7 
Mar 2016
5^{2}·11 Posts 
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 
20180324, 13:26  #8 
"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. 
20180324, 14:11  #9 
Feb 2017
Nowhere
6776_{8} 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 20180324 at 14:14 
20180325, 11:13  #10 
Mar 2016
5^{2}×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+2xyyy.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 
20180416, 23:54  #11 
Mar 2016
5^{2}·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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A primesieve for f(u,v)=u²+v²  bhelmes  Number Theory Discussion Group  28  20180211 00:28 
a primesieve?  bhelmes  Miscellaneous Math  9  20171117 21:09 
A Different Kind of a Computer  a1call  Miscellaneous Math  3  20170629 11:15 
So, is this some kind of record or what?  schickel  Forum Feedback  18  20110122 20:29 
A Kind of Solitaire  davar55  Puzzles  7  20070921 11:24 