Friday, September 12, 2014

Sophie Germain Primes

Growl. Here I am, back again. It's a good thing I wrote down all the things I want to cover this month. In the past, when I got this busy, I would end up avoiding the blog all together because I would have to think up a topic, research a bit, then write it. As much as the first step seems easy, when things are busy and I end up at home tired, trying to think of a topic to write about is near impossible. And funny thing is, I finished this yesterday. But then I got my fancy math machine working, my computer I can use for just doing programming and mathematics and such. Some people go through years of schooling, go to all the right places and meet the right people, then get an amazing job at a huge company where they do the work that puts them in history with people like Einstein and Maxwell and Leibniz.  I spend all my money on stupid crap, and build crappy versions of awesome tools with parts I beg from people. I will be lucky to be in the same group with Srinivasa Ramanujan.

What is a Sophie Germain prime number? If you can multiply the prime by 2 and add 1, and the answer is prime, then it's a Sophie Germain prime. For example, take the prime 29. 29 * 2 = 58. 58 + 1 = 59. Quick trick to prove if a number is prime or not: square the number, add 17, then divide by 12. If their is a remainder of 6, or if the calculator you use has .5 after it, then it's prime. In this case, 59 2 + 17 12 has a remainder of 6. So it's prime.

In the example above, 59 is called the safe prime. There's a good s&m joke there, but I'm too mature to make it. What's really cool about Sophie primes is this: 59 * 2 + 1 = 119. 119 is prime, so therefore 59 is a Sophie prime. 119 * 2 + 1 = 239. 119 is a Sophie prime. And so is 239. Same works for other Sophie Primes.

Like I said, I finished this yesterday. I didn't post it, because I also wrote this bash script for Sophie Primes. My month isn't going exactly as planned, but damn it I can at least attempt to try!

#!/bin/bash

echo "Please enter a number"
read NUMB
prime=$(($NUMB**2 + 17))
function e {
    prime=$(($1**2 + 17))
    if [ $(($NUMB)) -le 3 ]; then
       test =$(($NUMB * 2 + 1))
       echo "$NUMB is prime, and the safe prime is $test" 
    elif [ $(($prime % 12)) = 6 ]; then
       echo "$NUMB is a prime number"
       safe=$(($NUMB * 2 + 1))
       sophie=$(($safe**2 + 17))
       if [ $(($sophie % 12)) = 6 ]; then
          echo "$NUMB is a Sophie prime! The safe prime is $safe"
          exit
       else
          echo "$NUMB is prime, but it's not a Sophie prime."
          exit
       fi
    else
       echo "This number is not prime"
       exit
    fi
}
e $NUMB

It's fairly simple code, really. It uses the prime test I discussed early to test if a number is prime or not. If it is, then it multiplies it by 2 and adds one, then tests if that number is prime. Simple. Problem is this: the prime test does not work for numbers less than or equal to three. So there is a special case to check if the number entered is < 3. This is written in bash, which is not that powerful, so it does not like big numbers. If you give it 1000000000000066600000000000001, which is prime, it just says "Not prime". This is because the result of the prime test is too large to store in it's memory.

Questions, comments, thoughts? Leave them below.

1 comment: