Thread Closed

strong primality test ... ??

 
Share Thread
Apr26-05, 07:57 PM   #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:
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
PhysOrg.com science news on PhysOrg.com

>> City-life changes blackbird personalities, study shows
>> Origins of 'The Hoff' crab revealed (w/ Video)
>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
Apr28-05, 02:18 PM   #2
 
bump ...

anyone?
May1-05, 07:26 PM   #3
 
ANYONE? bump one last time as its due tomorrow and im still stuck
Thread Closed

Similar discussions for: strong primality test ... ??
Thread Forum Replies
Enthalpy of Neutralisation Strong acid + Strong base Biology, Chemistry & Other Homework 10
Translating a strong induction to test cases if valid or invalid? answers given Calculus & Beyond Homework 0
Another (candidate) test of primality of Mersenne number Linear & Abstract Algebra 11
primality testing Calculus & Beyond Homework 2
A primality test for Fermat numbers faster than Pépin's test ? Linear & Abstract Algebra 2