How do you even generate a large random prime number with more than 100 bits?

How do you even generate a large random prime number with more than 100 bits?

Other urls found in this thread:

en.wikipedia.org/wiki/AKS_primality_test
crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf
en.wikipedia.org/wiki/Miller–Rabin_primality_test
random.org/
random.org/faq/#Q2.1
twitter.com/AnonBabble

first
it is impossible to generate "random" number

pseudo random

just loop trough all the bits and randombly flip them into 0 or 1

how do you check if's a prime number?

with a complex bitwise mathematical algorithm pattern function

do you know any?

If you want the meme cs degree approach:

isPrime = true
for (int i = 0; i < num; i++) {
if (num % i == 0)
isPrime = false
}

en.wikipedia.org/wiki/AKS_primality_test

no but they must exist, i cannot believe they wouldn't

Does this work? I think it might. I mean if no integers up to the num are evenly divisible then it must be prime...

Im probably autistic, but other than the resource usage of this whats wrong with it?

>but other than the resource usage of this whats wrong with it?
the resource usage. brute forcing it's highly inefficient

Non-trivial question with some interesting cryptographic properties.

Firstly, don't. It's 2017. Don't use finite-field Diffie-Hellman or RSA. Use robust elliptic curve primitives: X25519, Ed25519, X448, Ed448, maybe as part of the Noise protocol framework. (You probably shouldn't try anything post-quantum yet because unless you really know what you're doing, you're going to have a bad time. Wait a few years.)

Let's assume you're doing RSA anyway.

Obviously, start with a good cryptographically secure pseudo-random number generator, seeded with as much true entropy as you can collect.

From there, you have the trivial approach, basically do { num = csprng() } while(!primality_test(num)); That's unbiased, and if your primality tests are good enough (let's assume they are) should work fine, unless you need a safe prime (in which case, also test for safe primes). How many times will you have to run that? Wow, you might worry about how long the runtime will be.

So of course, nobody actually does that. They all have "optimised" approaches - for example, as described in FIPS 186-4.

Or one efficient one by Joye/Paillier which generates p=kM+(randprime^a mod M). Some of these optimised approaches are pretty much okay as long as you get them exactly right, but this makes them a very fertile ground for backdoors like making randprime=65537 (like Infineon, so the NSA could factor keys with Howgrave-Graham/Coppersmith)! - Paper: crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf

en.wikipedia.org/wiki/Miller–Rabin_primality_test

this is the test most commonly used for practical purposes.

Ok yeah hence the meme cs degree

So, basically, to reiterate - don't. It's incredibly easy to fuck up the old finite-field stuff in a way that impacts security. You have to do it exactly right, and your only chance of that is use a library that is open, has been incredibly thoroughly audited, and hope. Enough eyes have looked at GnuPG by now, and (since the LibreSSL "valhalla"), at OpenSSL/LibreSSL/BoringSSL too. But even there you should probably avoid RSA wherever you can.

Use RFC7748 elliptic curves. Specifically, use libsodium because that makes it easy as hell.

djbesus spent time on it, so you don't have to use the old clunky shit or curves of dubious provenance that break a million ways. That basically takes 32 random bytes from your OS csprng (don't make your own!), clamps off a few bits and you're done (because the curve has a complete addition formula).

If you're doing something that talks to something else, I suggest using the Noise protocol framework by Trevor Perrin. It is incredibly good and robust, like a billion people use it every day (in WhatsApp) without knowing or caring, and it frustrates nation-states. It'll do.

run it and find out dumbass

Actually even for security applications you don't tend to be certain you have a prime you've just made it excessively likely.
I know it sounds like BS but it's a very common and profitable tradeoff.

no it doesn't work, num % 1 is always 0

You'd get an F for that prime checker mr meme cs degree.

>Use robust elliptic curve primitives
Hi NSA

Change the for loop to start counting from 2 and only check up to the square root of the number you are checking.

this was one of the first gifs i ever saved

so cute :3

No? are you retarded? 5%2 is not 0

sorry didn't see that the int i started at 0 lol

Also, change the increment from 1 to 2. Why are you checking if even numbers are prime like a brainlet?

holy shit same

>using primitive integer type
your compiler is going to have integer expand to either 64-bit or 32-bit data types, so it can't handle the 100 bits OP is asking for
>num % 1 == 0 is always true
so apparently no numbers are false in your world
>testing all the way up to num instead of sqrt(num
>checking even numbers
u wut.

with that modification the code will still erroneously set isPrime to true for num

>Use RFC7748 elliptic curves. Specifically, use libsodium because that makes it easy as hell.
Notice how this shill detected people who want to roll their own non-compromised crypto and he is trying to bring them back to the pastures of backdoored libraries.

No thank you.

but is it possible to generate a random pseudo-number?

Start generating numbers of the length you want (e.g. 1000 digits or whatever) then run them through a "prime sieve" to rapidly eliminate most of the composite numbers. Then once you've got a number that "might" be prime you run the actual rigorous check for divisibility by lower primes.

>with that modification the code will still erroneously set isPrime to true for num

Excuse me, Mr. num? Are you less than or equal to 1?

Generate large number, cast to string, concatenate 1 and cast back lol

You generate them just like you generate any other number. The problem is knowing which ones will be prime.

yes, you just have to psuedo-generate a number randomly.

>O(n^2)
Just use a primality test such as Miller-Rabin, idiot

Is there any proof the library is compromised, or are you just spewing shit? It's all open source, surely someone had audited it if it's so popular

Watch your tone chump

It is possible.
random.org/

RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.

random.org/faq/#Q2.1

>Oddly enough, it is theoretically impossible to prove that a random number generator is really random.

How'd I do, lads:
import os
from primes import is_prime


def get_large_prime(bits):
if bits % 8 != 0:
raise ValueError('bits must be a multiple of 8')
prime = 0
while not is_prime(prime, k=15) or len(format(prime, 'b')) < bits:
prime = int.from_bytes(os.urandom(bits // 8), 'little')
return prime

print(get_large_prime(104))

$ time python3 test5.py
20008979862427452740978326442923

real 0m0.036s
user 0m0.032s
sys 0m0.000s
is_prime is my own implementation of Miller-Rabin, but quite slow in Python
On Linux, /dev/urandom will return cryptographically secure bytes. So yes, it is as far as can be distinguished. It uses hardware entropy sources

...

Why do you think this is O(n^2)

it's very clearly O(n). In fact, it's ϴ(n) since the faggot who coded it doesn't exit the loop on finding out it's not prime, and always runs through it num times.