4 ms·

Thanks for the summary. > First check the remainder modulo 10, modulo 9 and modulo 24. This makes zero sense already. First, 9=3 x 3, so checking for 3 is suf

Thanks for the summary. > First check the remainder modulo 10, modulo 9 and modulo 24. This makes zero sense already. First, 9=3 x 3, so checking for 3 is sufficient. (Checking for 9 might be easier in decimal, but why the hell would you do cryptography in decimal?) Then there’s the 24=2 x 2 x 2 x 3. Again, why not just use 6, but even worse, there’s no new factor here that’s not already covered by 10 and 9. (And as you mentioned, even if this works, much better primality Tests are readily available.) (Off-topic: Is there a good way to indicate multiplication on HN? I can’t figure out how to escape asterisks, and Unicode symbols seem to be simply filtered out, which is a bit crazy in 2019.)

YeGoblynQueenne 7y ago
Try typing two asterisks with a space in between: *
thaumasiotes 7y ago
> Checking for 9 might be easier in decimal It isn't. The test is the same in both cases.
- rurban 7y ago
  It is. The sum of decimals is much faster than the modulo.
  - thaumasiotes 7y ago
    Huh? You need modulus either way. n is zero (mod 3) iff its digit sum is zero (mod 3), and it's zero (mod 9) iff its digit sum is zero (mod 9).
gus_massa 7y ago
They are using the "rule of nines" (i.e. the sum of the digits, perhaps iterated). It is very handy when you have the decimal representation of the number to operate on paper, but it's not as handy when you have the numbers in the computer. I "translated" that to "modulo 9" because it is equivalent and is easier to understand for not native English speakers. [Hi from Argentina!] Also, they are using the last digit of the number, that I translated to "modulo 10". Another reason for the translation is that the mathematical structure is more clear in "modulo 10, modulo 9 and modulo 24" than in the version "last digit, nines rule and modulo 24". In a computer is much more efficient to use modulo that transforming the number to a string and then operating with the digits, so I hope they have an efficient implementation but it is not clear from the pdf.
qtplatypus 7y ago
It looks like a pen and paper algorithm adapted to computing. Though even then it sucks. Mod 2, mod 5, mod 3 would eliminate more non primes and require less steps in pen and paper.

YeGoblynQueenne 7y ago

Try typing two asterisks with a space in between: *

thaumasiotes 7y ago

> Checking for 9 might be easier in decimal It isn't. The test is the same in both cases.

rurban 7y ago
It is. The sum of decimals is much faster than the modulo.
- thaumasiotes 7y ago
  Huh? You need modulus either way. n is zero (mod 3) iff its digit sum is zero (mod 3), and it's zero (mod 9) iff its digit sum is zero (mod 9).

gus_massa 7y ago

They are using the "rule of nines" (i.e. the sum of the digits, perhaps iterated). It is very handy when you have the decimal representation of the number to operate on paper, but it's not as handy when you have the numbers in the computer. I "translated" that to "modulo 9" because it is equivalent and is easier to understand for not native English speakers. [Hi from Argentina!] Also, they are using the last digit of the number, that I translated to "modulo 10". Another reason for the translation is that the mathematical structure is more clear in "modulo 10, modulo 9 and modulo 24" than in the version "last digit, nines rule and modulo 24". In a computer is much more efficient to use modulo that transforming the number to a string and then operating with the digits, so I hope they have an efficient implementation but it is not clear from the pdf.

qtplatypus 7y ago

It looks like a pen and paper algorithm adapted to computing. Though even then it sucks. Mod 2, mod 5, mod 3 would eliminate more non primes and require less steps in pen and paper.