Recent content by Milkman

Does anyone know why the lucas-lehmer test won't work with numbers represented by polynomials? The modulus polynomial does not divide the last term correctly for some reason. Example (the code boxes are polynomial long division): the numbers will be represented in base 4, so 4 = x p = x + 1...

Multiplication works perfectly now, but I'm wondering about division. If i wish to divide two sequences of numbers with an ntt, would I just ntt those two sequences, and multiply the first sequence's terms by the modular inverse of the second sequence's terms? Is division even possible to do...

Thank you shmoe, I understand exactly what's going wrong now. In order to be absolutely sure that a polynomial can be squared using this method without any problems, I think that this inequality must evaluate true: (d+1)(m-1)^2 < p where d is the degree of the polynomial, m is the base used...

Yes, here is a list of results that i get in base 16 and 17, for an ntt with a modulus of 17, length of 16, and primitive root of 3. base16 base17 num num^2 result result 16 256 256 17 289 289 289 18 324 324 324 19 361 361...

Hello everyone, I'm new to this forum, and I've registered to seek advice on this topic. What I'm attempting to do is multiply two very large numbers together, represented as polynomials, by the use of the number theory transform (ntt). I've done much research on this topic and I've had some...