2
$\begingroup$

Im trying to implement the Lucas Primality test as described in FIPS 186-3 C.3.3. However, ive hit a problem:

im just testing my code with the value 33, im getting $D = 5$ as the first value for $\left(\frac{D}{33}\right) = -1$. with that, at step 6.2 for starting value $i = 4$ im getting $V_{temp} = {{{1 * 1 + 5 * 1 * 1} \over 2} \mod 33} = 3$. then, in the if/else block, there is a $"V_i ="$ step. since at $i = 4, k_i = 0$, the step taken is $V_i = V_{temp}$, how do i stuff 2 bits into a $V_i$? am i supposed to add? bitwise or? do i mod the value by 2 before i set the bit?

// integer is a custom arbitrary precision integer type i wrote // it's supposed works like a normal signed int // integer::bits() returns the length of the value's binary string // integer::operator[] returns the bit at whatever given index, with index 0 being the least significant digit and bits() - 1 being the most significant digit  bool Lucas_FIPS186(integer C){     if (perfect_square(C))         return 0;     integer D = -3;     bool flip = false;     integer j = 1;     while (j != -1){         D = abs(D) + 2;         if (flip)             D = -D;         j = jacobi(D, C);         if (j == 0)             return 0;         flip ^= 1;     }     integer K = C + 1;     integer U = 1;     integer V = 1;     for(unsigned int i = K.bits() - 1; i > 0; i--){         integer Utemp = (U * V) % C;         integer Vtemp = (((V * V) + (D * U * U)) / 2) % C;         if (K[i - 1] == 1){             U = (((Utemp + Vtemp) / 2) % C);             V = (((Vtemp + D * Utemp) / 2) % C);         }         else{             U = Utemp;             V = Vtemp;         }     }     return !(U == 0); } 

EDIT: The code has been updated. 33 is still a problem. I also tested a very large known composite, and it returned prime

  • 0
    Maybe this would go over better on the programming website.2012-06-26

1 Answers 1

2

There's no reason to treat U and V as bit sequences. each $U_i$ and $V_i$ is a residue $\bmod C$ that should be stored as an integer.

[Edit in response to the edit in the question:]

You're taking the division by $2$ too literally. Note the explanation following the algorithm in the file you linked to:

Steps 6.2, 6.3.1 and 6.3.2 contain expressions of the form $A/2 \bmod 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 \bmod C$ may be calculated as $(A+C)/2 \bmod C$. Alternatively, $A/2 \bmod C = A\cdot(C+1)/2 \bmod C$, for any integer $A$, without regard to $A$ being odd or even.

  • 0
    how did i miss that?2012-06-26