Applied Cryptography: RSA - Finding Large Primes - Part 3

[@aymenahdibi1251]

i really appreciate your tutorials , awesome explanation, BIG UP for your effort ,your channel need to be more famous

[@leandrojunes7091]

I appreciate that!

[@peterribers]

If the purpose of finding a prime is using it for RSA, why not go backwards generate an uneven r by random and multiply by 2 (choosing u = 1) get p-1. This way you dont need to find u and r FROM p. Furthermore the test algorithm would be a little simpler (no loop from 1to u is needed) AND the running time would also be little shorter. The consequence would be of course that half the possible primes is discarded, but that does not really matter. Adding a single ekstra bit to the codelength would compensate for it anyway. It is not amatter of great importance, but it is always nice if you can make things simpler. I could just do so in my own implementation, but I would like a comment on this idea.

[@steveking7719]

Why don't you design a PRG that generates random numbers that only end in 1,3,7, and 9. THAT.... would increase your probability of generating a prime.

[@peterribers]

I agree. However in at later video it is sugggested to run at pretest on all small primes up to 100 by simple division before running miller-raben. This adresses the issue to som extent. Instead of genrating random numbers in a compleetly naiveway and then testing, you should consider how your random generator and your testing up to 100 could be merged/optimized into a joint algorithm.

[@syedmdabid7191]

It's no good of watching. It ain't confirmatory test to be prime for a big number.