I am trying to follow the steps to the Lucas Probabilistic Primality test, given on 83 of The Federal Information Processing Standards Publication Series of the National Institute of Standards and Technology. I found this document by searching and would first like to confirm the test described in C.3.3 really is the Lucas probable prime test (also described in wikipeida)? Or is this something different? (Though the test seems common enough, I had trouble finding good reference material)

I do not understand these steps

$U_{temp} = U_{i+1}V_{i+1}mod C$

$V_{temp} = \frac{V_{i+1}^2+DU_{i+1}^2}{2} modC$

For more context:

section of refereed text

I thought $U_{i+1}$ and $V_{i+1}$ represented 0s and 1s (binary). So what does it mean when they're written side by side like that? Somehow 'multiply' them? Or does $U_{temp}$ and $V_{temp}$ consist of two bits each? In the second line how does squaring make sense when applying it to bits?

What is meant by $K_rK_{r-1}...K_o$ is the binary expansion of $K$? Is $k_i \in$ [0, 1] or [0,1,2,3,4,5,6,7,8,9]?


All arithmetic is done $\!\bmod C$, so all integers $U_j$ and $V_j$ lie in be in the range $\,0\le n < C-1.\,$ Thus the expression $\,U_j V_j\bmod C\,$ means to multiply these integers then reduce the product modulo $C$.

The $K_i$ are indeed the binary digits of $C+1$. They are used analogously as in repeated squaring to decide whether to multiply or square, e.g. see the binary Horner polynomial viewpoint I describe here, and see this Wikipedia section.

  • $\begingroup$ Darn. I would have awarded you the bounty but had computer troubles and now it expired. $\endgroup$ – northerner Jul 13 '19 at 9:28
  • $\begingroup$ Is it possible for $U$ and $V$ to be negative? $D$ can be negative and it's used in calculating $V_{temp}$. I'm assuming in $DU^2_{i+1}$ only the U is squared, not the whole term? $\endgroup$ – northerner Jul 17 '19 at 20:33
  • $\begingroup$ @northerner Most implementations of mod normalize remainders to the range $\, 0\le a\bmod n < n$ $\ \ \ \ $ $\endgroup$ – Bill Dubuque Jul 17 '19 at 20:38
  • $\begingroup$ I think I may have misunderstood greatly. Does $U_r$ and $V_r$ represent the r-th term in a sequence? Or does it represent the value at the r-th digit of the number? Because step 4. talks about binary representation so is step 5. also being expressed in binary? $\endgroup$ – northerner Jul 24 '19 at 11:19
  • $\begingroup$ @northerner The former. Only $K_i$ refers to binary digits. $\endgroup$ – Bill Dubuque Jul 24 '19 at 12:47

These quantities are integers. So $U_{i+1}V_{i+1} \pmod C$ is a multiplication followed by a modular reduction.

Moreover, read the note at the end of section C.3 where it is explained how to interpret the division by 2, for implementors.

Steps 6.2, 6.3.1 and 6.3.2 contain expressions of the form A/2 mod C, where A is an integer, and C is an odd integer. If A/2 is not an integer (i.e., A is odd), then A/2 mod C may be calculated as (A+C)/2 mod C. Alternatively, A/2 mod C = A·(C+1)/2 mod C, for any integer A, without regard to A being odd or even.

This is further evidence of integer operations not bit operations. No primality test uses primitive bit operations, since prime factorization does not have a simple interpretation in terms of bits.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.