
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 25th, 2018, 02:17 PM  #1 
Member Joined: Jul 2010 Posts: 83 Thanks: 2  Problem with generating safe primes
So I'm using the Lucas primality test to generate large primes. The factorization of N1 is known of course and in this case I'm just using randomized powers 2 and 3. That part works fine and it produces plenty of primes. Now what I really want is "safe primes". Since I've already verified that N is definitely prime then I can also use the Lucas test to check if N*2+1 is prime (and thus a safe prime). Problem is this part of the test never passes. Any idea why a safe prime would never be in this form?

August 25th, 2018, 04:36 PM  #2 
Global Moderator Joined: Dec 2006 Posts: 20,370 Thanks: 2007  
August 25th, 2018, 06:32 PM  #3 
Member Joined: Jul 2010 Posts: 83 Thanks: 2  Very simple algorithm. Start with the product of all prime factors then repeatedly select one of the prime factors, multiply it with the current value, then perform a Lucas test. Crude but effective. For some reason those particular factors don't seem to be working out too well. Not sure why though.

August 25th, 2018, 07:17 PM  #4 
Global Moderator Joined: Dec 2006 Posts: 20,370 Thanks: 2007 
Starting with just 2 and 3 as prime factors? If so, why not use some other prime factor instead of 3?

August 25th, 2018, 08:39 PM  #5 
Member Joined: Jul 2010 Posts: 83 Thanks: 2  Larger factors just tend to spread out the search space in such a way that the whole process seems to take longer to find primes. Buy yeah. looks like I have no choice at this point. I guess Sofie Germain's (minus one) just don't ever have only 2 and 3 as prime factors.

August 26th, 2018, 06:04 AM  #6 
Member Joined: Jul 2010 Posts: 83 Thanks: 2 
Ah...just realized the problem. If a Sofie Germain prime minus one had 3 as a prime factor then the corresponding safe prime would also HAVE to be divisible by 3 itself!! [Just consider the expression ((K * 3 + 1) * 2) + 1] So mystery solved, the algorithm is now working as expected. I'm happy. 

Tags 
generating, primes, problem, safe 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Problem with primes  lua  Number Theory  4  January 17th, 2018 09:17 AM 