My Math Forum Problem with generating safe primes

 Number Theory Number Theory Math Forum

 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 N-1 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,926
Thanks: 2205

Quote:
 Originally Posted by Sebastian Garth I'm just using randomized powers 2 and 3.
How exactly?

August 25th, 2018, 06:32 PM   #3
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
 Originally Posted by skipjack How exactly?
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,926 Thanks: 2205 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

Quote:
 Originally Posted by skipjack Starting with just 2 and 3 as prime factors? If so, why not use some other prime factor instead of 3?
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 Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top