mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2018-01-15, 22:09   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default Proth and Riesel Primes

I may be missing something here, but why in the definition of Proth (k\cdot2^n + 1) and Reisel (k\cdot2^n - 1) is there the requirement that k < 2^n?

There are primes which exist when k > 2^n so is it for the purposes of more efficient primality testing?
lukerichards is offline   Reply With Quote
Old 2018-01-15, 22:15   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,861 Posts
Default

Quote:
Originally Posted by lukerichards View Post
I may be missing something here, but why in the definition of Proth (k\cdot2^n + 1) and Reisel (k\cdot2^n - 1) is there the requirement that k < 2^n?

There are primes which exist when k > 2^n so is it for the purposes of more efficient primality testing?
Otherwise all odd primes would fit both definitions.
The tests that we use to prove them prime rely on these conditions.
henryzz is offline   Reply With Quote
Old 2018-01-15, 22:26   #3
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by henryzz View Post
Otherwise all odd primes would fit both definitions.
Yes, of course! I knew I was missing something obvious!

So if, for example, one wanted to check the primality of 635466457083\cdot2^2-1 there's no *efficient* algorithm for so doing?

(It is prime btw... It's 2541865828331)

Last fiddled with by lukerichards on 2018-01-15 at 22:26
lukerichards is offline   Reply With Quote
Old 2018-01-20, 12:25   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,861 Posts
Default

Quote:
Originally Posted by lukerichards View Post
Yes, of course! I knew I was missing something obvious!

So if, for example, one wanted to check the primality of 635466457083\cdot2^2-1 there's no *efficient* algorithm for so doing?

(It is prime btw... It's 2541865828331)
There isn't an algorithm that scales to numbers anything like the size of proth and riesel primes for general numbers although there are efficient algorithms if the full factorization of N-1 or N+1 is known(and further extensions to partial factorization)
henryzz is offline   Reply With Quote
Old 2018-01-20, 12:46   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts
Default

Quote:
Originally Posted by henryzz View Post
There isn't an algorithm that scales to numbers anything like the size of proth and riesel primes for general numbers although there are efficient algorithms if the full factorization of N-1 or N+1 is known(and further extensions to partial factorization)
Interesting, thank you. So in this instance, because:

N+1 = 635466457083 * 2 * 2

An algorithm exists for efficient primality testing? Could you point me in the direction of those algorithms?

Also - my understanding is that there are various elements of number theory which help with primality testing when P can be written as E+1 or E-1, (where E is an even number) but that this gets significantly trickier where the known representation of P is O+2 or O-2 (where O is an odd composite number).

Does anyone know, or is anyone able to point me in the direction of anything useful, which might help with primality testing O +/- 2 or help with understanding why this is difficult.

I'm currently working on an algorithm which generates O, such that P = O +- 2 and seems empirically to be more likely to be prime c.f. 2p - 1. To test primality I could find E = P +- 1, but this feels inefficient.
lukerichards is offline   Reply With Quote
Old 2018-01-20, 13:09   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×35×7 Posts
Default

A good starting place for you would be this page. It does not mention KP (Konyagin-Pomerance) nor CHG (Coppersmith-Howgrave-Graham).
paulunderwood is online now   Reply With Quote
Old 2018-01-20, 13:30   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
A good starting place for you would be this page. It does not mention KP (Konyagin-Pomerance) nor CHG (Coppersmith-Howgrave-Graham).
Thank you!

In the extremely unlikely event that my general playing around ever discovers something new, I think a great amount of credit will have to be given to the GIMPS forum!
lukerichards is offline   Reply With Quote
Old 2018-01-20, 16:47   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

5·181 Posts
Default

Brillhart-Lehmer-Selfridge (1975) show over 30 forms of n-1, n+1, and hybrid factoring.

It doesn't help at all with n-2 or n+2 other than to give the proofs behind lots of the n-1/n+1 methods.

These methods work quite well for small numbers (say, less than 40 digits) but suffer from scaling issues in general as once into the 100+ digit range it just takes too long for the partial factoring. It's still worth checking for easy cases. If your input is constructed then perhaps even large inputs have a known partial factorization for p-1 and/or p+1. Remember that your proof relies on the factor primality as well so for non-trivial factors you get to recurse.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proth primes ET_ Proth Prime Search 8 2020-02-15 16:06
(NEW) Proth Primes Section kar_bon Riesel Prime Data Collecting (k*2^n-1) 6 2010-11-25 13:39
Riesel primes Primeinator Information & Answers 12 2009-07-19 23:30
Proth Riesel Drag Racing robert44444uk Math 1 2005-09-24 10:35
some primes I found with Proth.exe last year ixfd64 Lounge 1 2005-09-07 23:42

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

Wed Sep 23 23:45:15 UTC 2020 up 13 days, 20:56, 0 users, load averages: 1.63, 1.79, 1.77

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.