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