1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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
      while( A^2 mod n != 1 )
         A = A^2 mod n
      if( A = -1 )
         "maybe prime"
    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 ...

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

  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