My Math Forum Algorithm about primes

 Number Theory Number Theory Math Forum

 February 29th, 2016, 06:01 AM #1 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 Algorithm about primes Hi everyone, Here is my discovery. How to build the biggest prime ever? My algorithm illustrated by an example. Start with some primorial #17=2*3*5*7*11*13*17=510510 Compute a=int(sqrt(510510))=714 List the first few primes > 17 19,23,29,31,37,41.... You do not need to list them all up to the last prime < 714. Compute : b1=#17 = 18 mod 19 b2=#17 = 2 mod 23 b3=#17 = 23 mod 29 b4=#17 = 2 mod 31 b5=#17 = 21 mod 37 b6=#17 = 19 mod 41 .... Compute : c1=19-b1=1 c2=23-b2=21 c3=29-b3=6 c4=31-b4=29 c5=37-b5=16 c6=41-b6=22 ..... You do the computation until you a pair of primes (31,29). c4=29 is prime and 31 which is the fourth listed prime 31 is prime too. Once you reach the first condition above you have to check if both are > 17 (17 is the last prime of the primorial of #17). The second condition if fullfilled : 29>17 31>17 Compute the product of the pair 29*31=899 Add 899 to #17 = 510510+899=511409 Now compute : int(sqrt(511409))=715 715 is not prime and the last prime is < a (see above) Hence the third condition is fulfilled. Once the three conditions are fulfilled we can be sure that 511409 is a certified prime. I tried with many other values. I hope I did not miscalculate. It always works. I do not know how to prove my results. What I want to do is first to check my algorithm to see if there are counterexamples. If my result is sure then how to prove it. Thank you. In any case even if the discovery is confirmed it will have a huge impact on the number theory. Assuming that there is some mistake somewhere can we improve it to make it better? Thank you for your time and your help.
 February 29th, 2016, 09:15 AM #2 Newbie   Joined: Sep 2014 From: Portland, Oregon Posts: 15 Thanks: 8 Math Focus: Number Theory I think you'd need more discussion of expectations around how long it takes to find your examples. Try it with something not tiny like 10000# (it's less than 4300 digits so not very large). Compare to methods of Maurer and Shawe-Taylor. They also have search steps, though using Pocklington or similar BLS75 methods. They are used daily to construct 1024 to 8192 bit primes and of course work beyond that. Neither method gets close to effectively producing record size primes (ten+ million bits). Thanks from mobel
 February 29th, 2016, 10:02 AM #3 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 Thank you. But here the goal is different. First : Im not trying to build a prime for cryptography purpose. Easy to retrieve it because it is built on primorials. Second : I want more than a result. I want a proof that if some conditions are fulfilled then the number produced is certainly prime. For #p for example you will use only prime of the size of p Primorial 1.000.000.000.000.000 will require to test primes of 15 digits. Im not sure that you got the core of the method.
 February 29th, 2016, 10:50 AM #4 Newbie   Joined: Sep 2014 From: Portland, Oregon Posts: 15 Thanks: 8 Math Focus: Number Theory I understand that a crucial question was whether your method works. I didn't address that at all. I point out a counterexample below. I was mentioning other constructive proof methods, and pointing out that the "biggest prime ever" is very large. Let me try with 19. 19# = 9699690 a = 3114 At 47: b = 18 mod 47, c = 47-18 = 29. Both prime, both > 19. k = 19# + 47*29 = 9701053 l = int(sqrt(k)) = 3114 which is not prime We can be sure than k = 9701053 is a certified prime. But k = 563 * 17231. Thanks from mobel
February 29th, 2016, 11:19 AM   #5
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by danaj I understand that a crucial question was whether your method works. I didn't address that at all. I point out a counterexample below. I was mentioning other constructive proof methods, and pointing out that the "biggest prime ever" is very large. Let me try with 19. 19# = 9699690 a = 3114 At 47: b = 18 mod 47, c = 47-18 = 29. Both prime, both > 19. k = 19# + 47*29 = 9701053 l = int(sqrt(k)) = 3114 which is not prime We can be sure than k = 9701053 is a certified prime. But k = 563 * 17231.
It will help me for sure to more to fix the conditions required such as the number produced will be prime for sure.
Maybe there is a theoretical flaw to fix.

 February 29th, 2016, 12:29 PM #6 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 Observation : When you take #19+29 is divisible by 47 9699719=47*206377 and 206377 is divisible by 47 again but #19+47 is not divisible by 29 Maybe I need more conditions to improve my idea. Still thinking. Last edited by mobel; February 29th, 2016 at 12:56 PM.
 March 2nd, 2016, 04:43 AM #7 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 Here is my new draft. Im sorry my previous mistakes. Im too lazy to write a complete paper to show how to build a biggest prime. My method starting from an example Primorial 7 I compute : #7=2*3*5*7=210 What is the number A to be added to #7 such as #7+A will be prime for sure? Condition 1 : The integer number A must be : - either prime > 7 - or odd composite number with the lowest factor > 7 Here is the list of the potential candidates : 11,13 Condition 2 : The number A must not exceed the last prime < int(sqrt(#p+A)) I compute the int(sqrt(#7))=14 The last prime number < 14 is 13 Condition 3 : Sieving the set of the potential candidates I start by computing #7 mod 11 #7= 1 mod 11 Then #7=2 mod 13 If we add 11 to #7 = 221 will not be divided by 11. So we need to check if 221 is divisible by the remaining number on the list 13. 221 is divisible by 13. Hence 11 is removed from the list. The only number remaining is 13. 210+13=223 is then for sure a prime number. Our list here is very short. But as #p grow the list grow quickly. For #11=2*3*5*7*11=2310 the list of the potential candidates will be : 13,17,19,23,29,31,37,41,47 because int(sqrt(2310))=48 At this stage I still think that we do not need to check all the numbers of this list. I`m blocked as long as I did not find a way to check only few numbers to claim that the number created is for sure prime.

 Tags algorithm, primes

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mobel Number Theory 2 September 21st, 2015 02:44 PM caters Number Theory 67 March 19th, 2014 05:32 PM metinsariyar Number Theory 10 May 12th, 2011 12:09 PM billymac00 Number Theory 4 November 22nd, 2009 05:05 PM Euzenius Number Theory 3 October 14th, 2009 01:14 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top