How do you determine the values of m and k in a strong primality test?

  • Thread starter JaeSun
  • Start date
  • Tags
    Test
In summary, the conversation discusses the concept of strong primality tests and how they differ from weak primality tests. The algorithm for strong primality test is given, but the person is confused about where the variables m and k come from. They mention their notes which mention writing n-1 = 2^k m and checking certain values for 2^m. The person is seeking help in understanding this concept in order to complete their programming assignment.
  • #1
JaeSun
37
0
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. I am 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 don't know where m and k come from, which is what is keeping me from finishing the program ...

grrrrrr
 
Physics news on Phys.org
  • #2
bump ...

anyone?
 
  • #3
ANYONE? bump one last time as its due tomorrow and I am still stuck
 

1. What is a strong primality test?

A strong primality test is a type of algorithm used to determine if a given number is a prime number. It is considered more reliable and accurate than other primality tests.

2. How does a strong primality test work?

A strong primality test uses a mathematical formula or algorithm to check if a number is prime or not. It typically involves complex calculations and can be computationally intensive.

3. What is the difference between a strong primality test and other primality tests?

Unlike other primality tests, a strong primality test provides a definitive answer on whether a number is prime or not. Other tests may only provide a probabilistic answer, which means there is still a chance of error.

4. Is a strong primality test always accurate?

Yes, a strong primality test is always accurate in determining if a number is prime or not. However, the accuracy of the test may vary depending on the specific algorithm used and the number being tested.

5. What are the applications of a strong primality test?

A strong primality test has various applications in fields such as cryptography, number theory, and computer science. It is used to identify prime numbers, which are essential in many mathematical and scientific calculations.

Similar threads

  • Introductory Physics Homework Help
Replies
1
Views
792
  • Introductory Physics Homework Help
Replies
3
Views
192
  • Introductory Physics Homework Help
Replies
2
Views
1K
  • Introductory Physics Homework Help
Replies
30
Views
791
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Replies
6
Views
822
  • Introductory Physics Homework Help
2
Replies
41
Views
4K
  • Introductory Physics Homework Help
Replies
6
Views
5K
  • Introductory Physics Homework Help
Replies
2
Views
232
  • Introductory Physics Homework Help
Replies
2
Views
736
Back
Top