mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-03-23, 23:54   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52·11 Posts
Default 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
bhelmes is online now   Reply With Quote
Old 2018-03-24, 00:22   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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 ?
science_man_88 is offline   Reply With Quote
Old 2018-03-24, 00:54   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A816 Posts
Thumbs down

Can you explain what the word 'mersenne' is doing in the title?
Click-bait much?
Batalov is offline   Reply With Quote
Old 2018-03-24, 01:16   #4
bhelmes
 
bhelmes's Avatar
 
Mar 2016

1000100112 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
bhelmes is online now   Reply With Quote
Old 2018-03-24, 02:04   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by bhelmes View Post
the factors of mersenne numbers f are all of the kind f=1 or f=7 mod 8
And of specific form.
science_man_88 is offline   Reply With Quote
Old 2018-03-24, 02:39   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Batalov is offline   Reply With Quote
Old 2018-03-24, 07:38   #7
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52·11 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
bhelmes is online now   Reply With Quote
Old 2018-03-24, 13:26   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2018-03-24, 14:11   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

67768 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2018-03-25, 11:13   #10
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52×11 Posts
Default

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 is online now   Reply With Quote
Old 2018-04-16, 23:54   #11
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52·11 Posts
Default

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
bhelmes is online now   Reply With Quote
Reply

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 2018-02-11 00:28
a primesieve? bhelmes Miscellaneous Math 9 2017-11-17 21:09
A Different Kind of a Computer a1call Miscellaneous Math 3 2017-06-29 11:15
So, is this some kind of record or what? schickel Forum Feedback 18 2011-01-22 20:29
A Kind of Solitaire 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.