In several RFCs for encryption and authentication there are large prime numbers with vague statements about their proof as prime but I can't find how these are actually proven prime. I don't want to blindly trust magic numbers, I want to verify for myself that they are prime. For large 8192 bit primes like in SRP, how do I do this?
Non-deterministic solvers are useless as they only reduce the probability that the number isn't actually prime. 'Someone' could have provided a number that isn't prime but isn't detected by a non-deterministic solver in reasonable time or within the confidence the algorithm stops at. Perhaps they even search for these.
Large mersenne primes are easy to prove prime but these aren't mersenne primes AFAIK.
I've tried ECPP (elliptic curve primality proving) but it doesn't seem feasible given how long it takes. Even verifying the 1024 bit prime with ECPP takes 20 minutes.
So, how is this done, and how do I prove it was done correctly? SRP is the cornerstone of many authentication systems and it's rather important to know that someone out there isn't holding onto some factors of these 'primes'. Here's the RFC that includes the primes themselves at the bottom: ietf.org/rfc/rfc5054.txt
This (if I converted it right) is the 8192 bit prime in decimal form if you want to try anything on it:
bool IsAPrimeNumber = true;int number = 1090748135619415929450294929359784500348155124953172211774101106966150168922785639028532473848836817769712164169076432969224698752674677662739994265785437233596157045970922338040698100507861033047312331823982435279475700199860971612732540528796554502867919746776983759391475987142521315878719577519148811830879919426939958487087540965716419167467499326156226529675209172277001377591248147563782880558861083327174154014975134893125116015776318890295960698011614157721282527539468816519319333337503114777192360412281721018955834377615480468479252748867320362385355596601795122806756217713579819870634321561907813255153703950795271232652404894983869492174481652303803498881366210508647263668376514131031102336837488999775744046733651827239395353540348414872854639719294694323450186884189822544540647226987292160693184734654941906936646576130260972193280317171696418971553954161446191759093719524951116705577362073481319296041201283516154269044389257727700289684119460283480452306204130024913879981135908026983868205969318167819680850998649694416907952712904962404937775789698917207356355227455066183815847669135530549755439819480321732925869069136146085326382334628745456398071603058051634209386708703306545903199608523824513729625136659128221100967735450519952404248198262813831097374261650380017277916975324134846574681307337017380830353680623216336949471306191686438249305686413380231046096450953594089375540285037292470929395114028305547452584962074309438151825437902976012891749355198678420603722034900311364893046495761404333938686140037848030916292543273684533640032637639100774502371542479302473698388692892420946478947733800387782741417786484770190108867879778991633218628640533982619322466154883011452291890252336487236086654396093853898628805813177559162076363154436494477507871294119841637867701722166609831201845484078070518041336869808398454625586921201308185638888082699408686536045192649569198110353659943111802300636106509865023943661829436426563007917282050894429388841748885398290707743052973605359277515749619730823773215894755121761467887865327707115573804264519206349215850195195364813387526811742474131549802130246506341207020335797706780705406945275438806265978516209706795702579244075380490231741030862614968783306207869687868108423639971983209077624758080499988275591392787267627182442892809646874228263172435642368588260139161962836121481966092745325488641054238839295138992979335446110090325230955276870524611359124918392740353154294858383359 for (int n = number; n > 0; --n) { if (number % n == 0) { IsAPrimeNumber = false; }}System.out.println(IsAPrimeNumber);
Kayden Peterson
Assemble a compute cluster or a quantum computer.
Justin Cox
AKS is deterministic.
Hunter Jenkins
The probability of an adequately tuned Miller-Rabin test failing to detect a nonprime is many orders of magnitude less than the chance of a meteorite chunk falling from space and killing you. Hell, Miller-Rabin isn't hard to code yourself. Just implement your own version and run it for a month straight.
The whole point of nondeterministic algorithms is that they do things randomly, so there is no strategy that one can devise to "beat" them. You might as well try to "trick" 1,000,000 coin flips.
Brandon Roberts
AKS is very slow.
Cameron Hernandez
Miller-Rabin is not beaten by Carmichael numbers, so I'm not sure what you're trying to say. Besides, the reason that Carmichael numbers beat the fermat primailty test is because the fermat primality test makes incorrect assumptions about detecting primes. In other words, the fermat test is playing one game, and carmichael numbers are another game entirely. If the algorithm isn't playing the right game, of course it will lose.
Hell, I'm not even sure what you're trying to get out of this thread. If the current fastest methods of prime testing are too slow for you, what do you think Holla Forums can offer? Do you expect a random shitposter to devise a new efficient testing algorithm? Do you want an user to show a flaw in Miller-Rabin? Do you expect the NSA to say "Looks like he got us. Time to go home"?
If you're really so worried about your primes, just run a deterministic test for as long as you need.
Adam Evans
I want to know how these people 'proved' these primes. We are all putting massive trust in them, yet no one seems to know how it was done and there are no certificates of primality I've found.
Tyler Reyes
The existence of a certificate of primality that doesn't involve trust or running a primality test yourself is impossible.
Kayden Jackson
With a certificate of primality I could verify their work with much less hardware. But let's not get caught up in details; the first question is how did /they/ prove it?
Jayden Ramirez
They had a prime number inspector certify it for primality.
t. number checker
Dominic Perez
Generally these aren't "proved" primes. They just have a 1/(4^BIG_NUMBER) chance of being non prime. I think.
Logan Richardson
How would this certificate even look like? Either you have something you can test yourself or you trust someone's word. In the latter case you might as well trust the RFC.
Check my numbers.
Benjamin Butler
Just ignore I mentioned certificates, the math will be over your head.
Christian Morris
There are various algorithms to determine primality. They usually require a large cluster to run in any reasonable amount of time.
Christopher Cooper
Just answer my question you pretentious fag, you don't actually know who you are talking to.
What kind of certificate do you expect, a factorization of n-1?
Adam Williams
(Checked) (Checked)
I hereby issue one (1) certificate of primality to the above posts certifying that these digits have been checked & approved.
Logan Wood
Now you've got me genuinely interested in the math behind such a certificate. Are you talking about verification, like in P and NP? If that's the case, then the primality certificate is the prime number itself. The number can be verified in polynomial time to be a prime using any standard deterministic primality checking algorithm. The only other solution would be for the certificate to contain all the numbers that DON'T factor n, which would always be 2 through n-1 if n is prime. Checking these would take exponential time, so it would be a waste of time. If there were a faster way to verify the prime number, then that would just become a new primality testing algorithm.
Please tell me where my math is "too shallow".
Juan Cook
If there is an a coprime to n such that a^(n-1)/p is not congruent to 1 modulo n for every prime divisor p of n-1, n is prime.
But obviously, this requires a decomposition of n-1, which is the kind of info OP is looking for. Also obviously, this won't exist for 8192 bit numbers. I don't know what he's expecting if EC testing is too slow for him and he doesn't seem inclined to tell me.
Let's try this again seeing as the autists can't grasp the core issues here:
Someone is giving you a large number and telling you it is prime. How they know it is prime is not obvious from the RFCs. How did they know it was prime, specifically, what was it they did? Where is their work? How do you tell it is prime?
These numbers happen to be the foundation for almost all internet cryptography (standard groups for DH used in RFCs). Yet no one seems to know where they came from, or if they're even prime.
Jacob Torres
It has not been proven that fast non-quantum algorithm for breaking RSA doesn't exist, yet we use it everywhere. This as all over cryptography, I don't see what's so special about some large primes in this regards. All we have is "reasonable level of certainty" and even if we had proof of primality of those large primes, we would still have "only" reasonable level of certainty that the cipher can't be defeated in reasonable time.
Charles Reed
openssl prime -hex $(cat fuckhuge_prime_hex.txt)
If openssl thinks the number is prime, you can then check the source code to make sure that the algortihm isn't flawed. If that's not enough, use a deterministic algorithm. If you want the RFC to tell you how the prime was found, complain to the IETF or something. What the fuck more are you looking for?
Adrian Wright
they summon the prime wizard and ask that he grant their request
Nolan Jenkins
Randomized tests aren't certain -- but deterministic tests aren't either. You could have a cosmic ray bit flip. You run the randomized test long enough that the cosmic ray bit flip is more likely, and call it a day.
Aiden Wilson
They ran Rabin-Miller on it a few times. I understand your general problem, trusting random shit someone gives you is a stupid idea and happens with frightening frequency. What I don't understand is why you don't just AKS them. Yes, it'll take a while, that comes with the territory of 8192 bit numbers. Who cares? Do you want to be sure that it's a prime or not? If you want a quick check, RM them.
For what it's worth (almost nothing), the authors of the RFC used π in the definitions to suggest that they didn't put a backdoor in.
