7
$\begingroup$

Unsure whether this is the right forum for this question, worth a try.

The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many resources on the web states that this is easy, however, without further explanation why that is?

Furthermore, since miller-rabbin exits when a nontrivial square root of 1 is found, this can be used to find a factor to the carmichael number: $x^2 \equiv 1 = (x+1)(x-1)\equiv0\ mod\ N$, where N is the carmichael number we want to factor. Hence factors must be found using $\gcd(x+1,N)$ and $\gcd(x-1, N)$, correct?

Due to problems with strong liars, in some cases we will miss out on factors, is this a major problem? Since miller-rabbin tests only passes composites with a probability 1/4 is it correct to say that the chances of finding a factor is > 0.5?

Kind regards!

Improve this question
$\endgroup$
4
  • $\begingroup$ Maybe this will help: cs.berkeley.edu/~vazirani/algorithms/all.pdf#page=38 $\endgroup$
    – mikeazo
    Nov 6, 2012 at 14:28
  • $\begingroup$ I think that you have the right sketch: find a witness to the Miller-Rabbin test; since that's a liar to the Fermat test, you can efficiently exhibit a non-trivial factor of $N$ as $\gcd(x-1,N)$ or $\gcd(x+1,N)$, where $x$ is the butlast result in the Miller-Rabbin test. I see no reason why odds of success would not be $\ge3/4$ for each random base tested. $\endgroup$
    – fgrieu ♦
    Nov 6, 2012 at 15:57
  • $\begingroup$ @fgrieu: Thank you for answering. Could you perhaps elaborate a bit more on why you think the success rate should be >= 3/4 $\endgroup$
    – Nyfiken
    Nov 6, 2012 at 16:19
  • $\begingroup$ This is more of a self note but wanted to include any how - believe this website has a good description. Better late than never ! - As I understand it, we basically need to try the exponents (n-1/2), (n-1/4) and so on... $\endgroup$
    – Ravindra HV
    Jul 30, 2017 at 18:39

2 Answers 2

Reset to default
8
$\begingroup$

Yes, using Miller-Rabin with a random witness does give a practical factoring method. When you run the Miller-Rabin algorithm, it can end in one of three ways:

  1. The final value is not 1; this case causes Miller-Rabin to output "Composite"

  2. An intermediate value was not 1 or N-1, but the next value was 1; this causes Miller-Rabin to output "Composite"

  3. The initial value was 1; or an intermediate value was N-1; this causes Miller-Rabin to output "Probably Prime".

Case 1 will happen only if $W^{N-1} \neq 1 \bmod N$, however, that we get that inequality for Carmichael numbers only if $W$ is a multiple of a factor of $N$; in this case, $gcd(W, N)$ gives us a nontrivial factor.

For Case 2, well, that gives us a nontrivial value $X$ for which $X^2 = 1 \bmod N$; as you correctly point out, a nontrivial square root of $N$ immediately gives us the nontrivial factors $gcd(X+1, N), gcd(X-1, N)$

Hence, in the specific case of Carmichael numbers, if the Miller Rabin test outputs "Composite", we always have enough information to immediately factor. And, when Miller-Rabin is given a composite number, then it will output "Composite" with probability > 3/4; hence, a single iteration will allow us to factor with high probability.

In fact, for Carmichael numbers, the probability of success with Miller Rabin is actually > 7/8; Carmichael numbers are not the worse case for Miller Rabin.

This gives us a practical factorization method; however for pedantic reasons, it doesn't actually answer the question. It's not a poly-time algorithm; it is a probabilistic poly-time algorithm which, per iteration, has a good probability of yielding a factor, but it also has a probability of not finding a factor.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is there a rigorous proof somewhere that the probability of composite-declaring is more than $3/4$? $\endgroup$
    – user16972
    Mar 7, 2020 at 22:24
0
$\begingroup$

Try this (a description of the comment above - also blogged the same! + posted same in math.stackexchange.com) :

For each prime base (2,3,5,7,11...) try checking the remainder for the exponents under [(n-1)/2],[(n-1)/4],[(n-1)/8]...and so on. Once a number other than 1 is found then try :

gcd (x-1,n)

or

gcd (x+1,n).

It should result in one of the factors!

For example :

Moduluo : n=561 base : a=2

[a^(n-1/1)] mod (n) : (2^560) mod (561) = 1 [a^(n-1/2)] mod (n) : (2^280) mod (561) = 1 [a^(n-1/4)] mod (n) : (2^140) mod (561) = 67

gcd(561,68)=17

gcd(561,66)=33

561/33=17

561=3*11*17 !!

Related links :

http://mathforum.org/kb/message.jspa?messageID=5488111 https://en.wikipedia.org/wiki/Carmichael_number

Also see this answer.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Actually, this answer is essentially the same as the answer I gave 4 years ago, except I didn't spell out exactly what Miller-Rabin was (the question mentioned it, so I assumed he knew what it was) $\endgroup$
    – poncho
    Jul 31, 2017 at 19:21
  • $\begingroup$ It did look like it but I decided to include it any how for my reference as well in case I needed it! Guess the OP's aware of it too. My understanding is that there would about (n/2) cases where the remainder would not be 1 (as per quadratic-residue) which makes it consistent with OP's understanding. I guess I still did not say so in the answer I posted though! $\endgroup$
    – Ravindra HV
    Jul 31, 2017 at 19:35
  • $\begingroup$ Actually, if you choose $a$ randomly, we can show it works signficantly more often than 1/2 the time; IIRC (and as I said in my answer), it works at least 7/8 of the time. That should also be true if you try $a$ in succession (as you suggest); however, we don't have a proof of that... $\endgroup$
    – poncho
    Jul 31, 2017 at 19:40
  • $\begingroup$ From what I understand, its less redundant if we use prime bases. While I do indeed do not have a formal proof, its possible to show the redundancy through examples. Given a base 'x' with a non-trivial remainder and another base 'y' with 1 as remainder then the remainder for base x*y will be non-trivial. $\endgroup$
    – Ravindra HV
    Jul 31, 2017 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.