Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Strong primality test ?

  1. Apr 26, 2005 #1
    strong primality test ... ??

    ok, bear with me ...

    we learned weak primality tests (given n and base a,::: a^(n-1) mod n ::: if it does not equal 1, then its composite, if it equals 1, then MAYBE prime) ...

    then we learned strong primes .... think of n-1 = m2^k when m is odd. test ::: a^m mod n and keep squaring until we get 1 (or past n-1). go back one step, and check if it was -1 (if so, probably prime, if not, then it is composite)

    so my homework. im kinda confused.

    I was given this algorithm for the strong primality test

    Code (Text):
    n-1 = m2^k
    A = a^m mod n
    if( A=1 )
      "maybe prime
    else
      while( A^2 mod n != 1 )
      {
         A = A^2 mod n
      }
      if( A = -1 )
         "maybe prime"
      else
          "composite"
    my question is, where does m and k come from??

    i been looking at my notes over and over again ... i did read that m is odd, so I can just choose any random odd number ? but then k ? what number is that?

    i am kinda lost ...

    other notes that i have:

    write n-1 = 2^k m
    check 2^m, (2^n)^2, ... , (2^m)^(2^k)
    if 2^m mod n = 1, n is like a prime. otherwise find first j so that:
    (2^m)^(2^j) != 1 and
    (2^m)^(2^j+1) = 1
    then 2^(m2^j) is a root of x^2-1 =0
    if 2^(m2^j) = -1, n is like a prime, if not, n is composite ...

    can anyone help??

    he went over this in like 1 day, way back in the beginning of the semester, and he just gave us this assignment .... would like any help in understanding this, so I could program this (the assignment is to program numbers that pass weak test, but fail strong test) .....

    i dont know where m and k come from, which is what is keeping me from finishing the program ...

    grrrrrr
     
  2. jcsd
  3. Apr 28, 2005 #2
    bump ...

    anyone?
     
  4. May 1, 2005 #3
    ANYONE? bump one last time as its due tomorrow and im still stuck
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook