My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
August 25th, 2018, 03: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?
Sebastian Garth is offline  
 
August 25th, 2018, 05:36 PM   #2
Global Moderator
 
Joined: Dec 2006

Posts: 19,870
Thanks: 1833

Quote:
Originally Posted by Sebastian Garth View Post
I'm just using randomized powers 2 and 3.
How exactly?
skipjack is online now  
August 25th, 2018, 07:32 PM   #3
Member
 
Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
Originally Posted by skipjack View Post
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.
Sebastian Garth is offline  
August 25th, 2018, 08:17 PM   #4
Global Moderator
 
Joined: Dec 2006

Posts: 19,870
Thanks: 1833

Starting with just 2 and 3 as prime factors? If so, why not use some other prime factor instead of 3?
skipjack is online now  
August 25th, 2018, 09:39 PM   #5
Member
 
Joined: Jul 2010

Posts: 83
Thanks: 2

Quote:
Originally Posted by skipjack View Post
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.
Sebastian Garth is offline  
August 26th, 2018, 07: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.
Sebastian Garth is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 10:17 AM





Copyright © 2018 My Math Forum. All rights reserved.