20061114, 10:02  #1 
Nov 2006
5_{10} Posts 
Number Theorem
Based on the theorie of numbers  Fermat and MillerRabin, i'm able to prove with a probability of 12^n if a number is prime or not.
But what if i wanted to proof that a prime number has a diffenter probability. Say x is prime with a probability of 10^n??? Thanks. Best Regards Nuno 
20061114, 11:25  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,563 Posts 
Quote:


20061114, 11:37  #3 
Nov 2006
5_{16} Posts 
post
what i would like to figure out is if there is any way to prove that a given number is a prime with a probability less than 10^n.
Based on MillerRabin algorithm we can only say that a number as a probability of being prime of 2^n. Can you help with it? Thanks 
20061114, 12:15  #4  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,563 Posts 
Quote:
Quote:
Last fiddled with by retina on 20061114 at 12:17 Reason: Stupid typos 

20061114, 12:16  #5  
"Bob Silverman"
Nov 2003
North of Boston
5·1,493 Posts 
Quote:
It is gibberish. To begin with, 12^n is *negative* for all n > 0. Secondly, you blather about variables x and n without defining a relationship between them. Finally, A *given* number is prime with probability 0 or probability 1. 

20061114, 12:18  #6 
Jun 2003
The Texas Hill Country
1089_{10} Posts 
herege,
"with a probability less than 10^n" does not make sense. For example, with n=3, you are asking for "a probability less than 1000". Similarly, in your original question "with a probability of 12^n" translates into "a probability of 7". Perhaps you can again try to get the correct limit on the probability that you seek. If so, then we might be able to understand your question. 
20061114, 12:29  #7  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,563 Posts 
Quote:


20061114, 12:34  #8 
Nov 2006
5_{8} Posts 
Ler
I posted it in the wrong way.
Let me correct: Based on MR we can assume that p is prime with a probability of 12^n. What i wanted was a way to make an algorithm capable of showing that p is prime with a probability of 110^n, that is with an error less than 0.001 Thanks 
20061114, 12:41  #9  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,563 Posts 
Quote:
Quote:
Try to understand that testing with more and more bases can increase your confidence that the given number is prime. Error rates don't seem to be relevant unless you can't trust you computer system to run the tests. Oh, yeah, how does p relate to n? Are they supposed to be the same number? R. D. Silverman has already raised this point with you. Last fiddled with by retina on 20061114 at 12:43 Reason: Added Q about p and n relationship 

20061114, 13:02  #10 
Nov 2006
5 Posts 
Read
Thanks Retina for being so patient.
I'm studying the MR test right know. I beliave i'm starting to realize how it works. So based on it, i got the following: If there are any solutions for x^2 = 1 (mod n) besides 1 or 1, then n is not prime. So with MR algorithm if i test a given number n for primality, and give it a number x < n, i might get that the number n may be prime with a probability of 12. So if i execute the algorithm a few times, the probability becomes 12^n. What i have to figure out is how to have an algorithm that i can say that for a given number, i can say about it that the probability of being prime is less than 10^n Thanks for your answers. Best ragards 
20061114, 13:19  #11  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1100110100011_{2} Posts 
Quote:
Quote:
Let's say you have in your head n=9, then you want a probability of correct result of 110^9. Note that the number is approximately 12^30. so if we do 15 trial MR test bases that would seem to give a prob of ~12^(2*15). Am I making any sense? It has been a while since I last programmed an MR test. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic  Nick  Number Theory Discussion Group  0  20170107 13:15 
Basic Number Theory 8: equiv. relations and Fermat's little theorem  Nick  Number Theory Discussion Group  0  20161110 23:10 
Basic Number Theory 6: functions and the Chinese Remainder Theorem  Nick  Number Theory Discussion Group  4  20161031 22:26 
My(?) Three body theorem.  davieddy  Math  1  20110808 03:14 
Another vindication of Gödel's Theorem?  devarajkandadai  Miscellaneous Math  1  20060922 17:43 