> 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.)
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.
It isn't. The test is the same in both cases.
The famous 19th century English poet Robert Browning was not a particularly worldly fellow and got it into his head that the word "twat" referred to a nun's headgear. Later he wrote a poem that needs a rhyme for bats in the context of religious folk arriving for prayer and he picked "twats", - then since he was an important English writer and this word was unfamiliar to them (or at least they had no citations for it) the editors of the Oxford English Dictionary asked him about it, and discovered his error. Oops. You're never going to make a mistake that'll be as famous as Browning's, so you're fine.
I also was thrown off by the word module. I said to myself, unless he is talking about modulo I have no idea what that is.
The Module Learning With Rounding (MLWR) and Module Learning With Errors (MLWE) problems are used for a couple of the round-two candidates in NIST's Post-Quantum cryptography contest.
Which makes it more confusing. Modules aren't first/second year university math.
Ignoring the reference to unrelated results about prime numbers, the main idea is that to check if a number is prime:
1) First check the remainder modulo 10, modulo 9 and modulo 24. This part is correct, but it's suspicious that they waste a few pages to prove it. Anyone with a minimal background will agree with this part explained in a line.
2) They make a multiplication table "Q-grid" of the number that are not multiple of 2 nor 3. The idea is that after discarding the numbers with the bad remainder module 24, the rest of the numbers are not multiple of 2 nor 3. Again, it's suspicious that they give a long explanation and the use of invented names like "Quasi-primes"
3) To test if N is prime, they try to find in this table build looking first at the numbers nearby the x~=sqrt(N) and y~=sqrt(N) so x * y ~= N. It's not clear how they lookup in the table.
Being very optimistic, this is essentially like searching for a divisor of N up to sqrt(N). [I'm not sure that their implementation is not worse.] This search up to sqrt(N) is one of the first trick you learn to test primality. The advantage of their method is that they reduce the search space modulo 24 and they get the result in sqrt(N)/3 steps. [I'm not sure that their implementation is not worse.] This is slightly better than using only the odd numbers to get the result in sqrt(N)/2 steps.
For big enough numbers to be used in cryptography, this sqrt(N) or sqrt(N)/2 or sqrt(N)/3 is complete rubbish compared to any modern serious method, it's not even funny, I understand the uproar.
Some quotes:
> And because when we search for the prime factors of some semiprime number we need to remove the non-prime numbers from both axes of the Q-grid, like 25, 35, 49 etc., the problem will automatically reduce to simply locating the number in the Q-grid, with its horizontal and vertical projections on both axes being its prime factors.
I hope they are not trying to build the whole Q-grid. It uses more memory than a simple search. Also if they are keeping only the prime numbers, why all the discussion of using the remainder module 24. All big prime numbers have the correct remainder module 24.
> In fact, these two numbers, 2 and 3, contradict many of the primes properties such that some mathematicians consider them as sub-prime integers.
I never hear that. Bad math joke: Did you notice that 2 is an odd prime number?