Number Theorem

[herege]

Pretty much.

I will try that. Thanks for your help.

Best regards.

[R.D. Silverman]

Originally Posted by herege

I posted it in the wrong way.

Let me correct:

Based on MR we can assume that p is prime with a probability of 1-2^-n.

Thanks

What is n??? If you are going to discuss mathematics, LEARN TO DEFINE
YOUR VARIABLES.

I suggest that you read a paper by Kim & Pomerance in Math. Comp.
I forget the exact title, but it is along the lines of "The probability that a
strong prp is composite".

If one runs MR n times on a candidate p, and it declares the number
prime, the probability that the declaration is in error is much lower than
2^(-2n). The exact probability depends on the size of p. If MR declares
a very large number (at least several hundred digits) to be prime, the
probability is VERY small that the declaration is in error.

Futhermore, each successive trial of MR on a given number (with a different
base for the test) is NOT INDEPENDENT of the preceeding trials. This is
(partially) what the Kim & Pomerance paper is about.

Once we have run MR with a given base (say b), and MR declares the number
prime, and we now run another trial with base b1, the probability of an
erroneous answer with base b1 is not independent of an erroneous answer
with base b. This is because once MR is run, a second run becomes
*conditional* on the first. The fact that the first trial declares a number prime eliminates a lot of candidates that might cause a second trial to err.

BTW, the use of the expression "probability that p is prime" is wrong
headed. p is either prime or composite. What should be said is that
p had been declared prime by a decision procedure and the probability that
the DECISION PROCEDURE IS IN ERROR is small. One can NOT say
"Based on MR we can assume that p is prime with a probability of 1-2^-n."
as you stated above. What we can say is that the probability that the
MR test is in error is 4^-n. (and yes, it is 4^-n, not 2^-n). A number
is either prime or it is not.

When one discusses probability, one MUST base the discussion upon
*random variables* having some probability density function. To do
otherwsie is meaningless blather.

Go read the Kim & Pomerance paper.

[R.D. Silverman]

Originally Posted by retina

Am I making any sense? It has been a while since I last programmed an MR test.

No, you are not making sense. And what has programming MR got to do
with understanding the math behind it??

Do us all a favor. If you are unsure about a subject, then KEEP QUIET.

[akruppa]

herege, from your posts my best guess is that you are looking for "logarithm base conversion."

Alex

[R.D. Silverman]

Originally Posted by akruppa

herege, from your posts my best guess is that you are looking for "logarithm base conversion."

Alex

A person who does not know to convert logarithms from one base to
another should probably not be participating in this forum. Their
math background is just too weak. I expect that anyone participating here
has mastered (not just passed) high school math through pre-calculus.
If they haven't, then discussions will be a total mystery to them.

I would never have guessed that herege was looking to solve 2^-n =
10^-k for k. I thought that he was asking how to achieve probability
10^-n with n trials of MR. The former is just too trivial a question.

[retina]

Originally Posted by R.D. Silverman

Do us all a favor. If you are unsure about a subject, then KEEP QUIET.

I don't accapt that statement. I was simply trying to help, if got something wring then so what. Everyone can correct me, or the mods can delete it, I don't mind. The important thing is that the intention is not to belittle or discourage. If one cannot give encouragement then that is the time to keep quiet.

[akruppa]

Asking how to convert logarithm bases is a valid math question, if at a pretty elementary level. Not sure if this thread should go into Miscellaneous... it's a beginner's question and was not very well stated, but at least it isn't a "look at teh uber-leet factoring algorithm I found" post.

Alex

[R.D. Silverman]

Originally Posted by retina

I don't accapt that statement. I was simply trying to help, if got something wring then so what. Everyone can correct me, or the mods can delete it, I don't mind. The important thing is that the intention is not to belittle or discourage. If one cannot give encouragement then that is the time to keep quiet.

"then so what"??

The answer is that one adds, rather than detracts from the confusion,
and a less than sophisticated reader would not know the difference.

Indeed, we already knew that the O.P. was less than sophisticated by
the nature of the original question. So how is such a person going to tell
that a supplied "answer" isn't correct?

[retina]

Originally Posted by R.D. Silverman

"then so what"??

The answer is that one adds, rather than detracts from the confusion,
and a less than sophisticated reader would not know the difference.

Indeed, we already knew that the O.P. was less than sophisticated by
the nature of the original question. So how is such a person going to tell
that a supplied "answer" isn't correct?

herege seemed quite satisfied with the result. That is enough for me. It seems the real question herege was asking was finally extracted and thus answered.

I doubt there is any harm in the method used to get there. "With so many mistakes we must surely be learning" (I can't remember who said it but it's a damn good quote). We can't all be right all the time, so mistakes and wrong conclusions will happen occasionally, and so what. It all gets fixed up in the end and we learn something because of it.

If the answer is not correct then there is no harm in someone else politely saying "umm, I think you made a mistake or misunderstood, a better answer is this ...".

Your response to herege about how the probabilty of each test being conditional on previous tests is indeed correct, but how did that help poor herege? herege, I feel quite certain, just needed a simple computation to satisfy his/her need. With you being so quick to measure the sophistication of herege but at the same time not realising that talking about conditional probabilities was most likely not helping seems to be somewhat poor judgement.

Originally Posted by R.D. Silverman

Go read the Kim & Pomerance paper.

Do you really think that herege, at his/her level of sophistication that you judged so easily, would be able to understand the Kim & Pomerance paper? Perhaps herege can understand given enough study time, but not everyone has oodles of time to devote to studying every piece of mathematical minutae.

[R.D. Silverman]

Originally Posted by retina

Do you really think that herege, at his/her level of sophistication that you judged so easily, would be able to understand the Kim & Pomerance paper? Perhaps herege can understand given enough study time, but not everyone has oodles of time to devote to studying every piece of mathematical minutae.

If you want to discuss a subject you need the pre-requisites.
If you are unwilling to do background reading then you should not
get involved.

Your attitude stinks. "oodles of time". If you are not willing to devote the
time to learning and reading what you need to know then take up another
subject.

Yet another instance of the "instant gratification" generation. A person
who wants to participate but is unwilling to spend the necessary time to
acquire needed background.

[R.D. Silverman]

Originally Posted by akruppa

Asking how to convert logarithm bases is a valid math question, if at a pretty elementary level. Not sure if this thread should go into Miscellaneous... it's a beginner's question and was not very well stated, but at least it isn't a "look at teh uber-leet factoring algorithm I found" post.

Alex

But the O.P. did NOT ask: how do I convert 2^-n to 10^-k? What was
asked was:

"1-2^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???"

Note the use of the word "diffenter (sic)" [different]. The O.P was
not asking how to convert 2^-n to an EQUIVALENT 10^-k, but was asking
for a different probability: 2^-n vs. 10^-n. Why else use the word "different"???

Asking "If 2^-n = 10^-k then what is k" is so totally a simple question
that it is hard to imagine from the gibberish posted that this is what the O.P.
intended. The wording of the original post strongly suggested that the O.P.
was trying to *improve* the probability of being wrong from 2^-n to 10^-n.

This math is only at the (U.S.) first year high school level or perhaps
the year before in a good math program.

You can't participate if you don't speak the language (math, not English).