Carmichael número factoring

Question

La tarea que me enfrento es implementar un poli-tiempo de algoritmo que encuentra un trivial factor de un número de Carmichael. Muchos recursos en la web que este es fácil, sin embargo, sin más explicación del por qué.

Además, desde Miller-Rabin sale cuando no trivial de la raíz cuadrada de 1 es encontrado, esto puede ser usado para encontrar un factor para el Carmichael número: $x^2 \equiv 1 = (x+1)(x-1)\equiv0 \pmod N$, donde N es el número de Carmichael queremos factor y $x$ el trivial de la raíz cuadrada de 1. Por lo tanto factores que deben ser encontrados usando$\gcd(x+1,N)$$\gcd(x-1, N)$, correcto?

Debido a problemas con fuertes mentirosos, en algunos casos, nos perderemos en los factores. Es este un problema importante? Desde Miller-Rabin pruebas sólo pasa compuestos con una probabilidad de 1/4, es correcto decir que las posibilidades de encontrar un factor es > 0.5?

Saludos!

Answer 1

Un número de Carmichael $N$ es probable prime, para cada base de $a$ coprime a $N$, pero hay una base $a$ $1<a<N$ no es demasiado grande y coprime a $N$ (si es que NO coprime a $N$, $gcd(a,N)$ es un non-factor trivial), de tal manera que $N$ no es muy probable primer a base de $a$. $a$ se llama a un testigo.

Para tal $a$, usted tiene $\large a^{2^d\times m} \neq -1\ (\ mod\ N)$ para todos los $d$$0\le d \le k$, cuando se $N=2^k\times m+1$ $m$ impar.

Pero para algunos $d$ $1\le d\le k$ (elija el más pequeño de tales $d$) ha $\large a^{2^d\times m}\equiv 1\ mod \ (\ N\ )$.

Pero la congruencia no se cumple para el exponente $d-1$ indstead de $d$. Nota, que $a^m\equiv 1\ (\ mod\ N)$ es imposible, si es un testigo.

Así, usted tiene una congruencia $x^2\equiv\ 1\ (\ mod\ N)$ , pero $x\ne \pm1\ (\ mod\ N)$ $gcd(x-1,N)$ es no trivial de factor de $N$ ($gcd(x+1,N)$ es un non-factor trivial).