Un estándar truco es trabajar con dos primos $p,q$ de la longitud de la $N$ donde $N$ es elegido para que los equipos puedan trabajar bien con los números de la longitud de la $N$, pero no con los números de la longitud de la $2N$. Para aclarar: $N$ tiene que ser lo suficientemente pequeño para que $A$ puede fácilmente producir números primos de longitud $N$ y puede extraer raíces cuadradas de los residuos cuadráticos módulo de tales primos, pero debe ser lo suficientemente grande como para que $B$ no puede factor general de los números de la longitud de la $2N$. (gracias a @TonyK para correctamente lo que sugiere que es preciso aclarar aquí).
Si $A$ tiene dos primos de ella puede entregar su producto, $n=pq$, $B$ que no se puede recuperar $p,q$. $B$ a continuación, se lleva a $m\pmod n$ y se calcula el $m^2\pmod n$, que luego manos a $A$ (para ser claros, que las manos de los residuos de la clase de $m^2$, no $m$).
Ahora, desde la $A$ conoce $p,q$ ella se puede encontrar la raíz cuadrada de $m^2$ modulo ambos $p,q$. Ay, que da lugar a cuatro posibles valores, vamos a llamarlos $\pm m, \pm k$. Ella adivina que un $B$ comenzó con manos y que de regreso. Si ella está en lo cierto, ella gana. Si ella está mal, $B$ ahora puede factor de $n$ y así demostrar que $A$ estaba equivocado, y, a continuación, $B$ gana.
Es un pequeño ejercicio para demostrar que $B$ factor de $n$ dado a los cuatro raíces cuadradas (tenga en cuenta que $\gcd(n,m+k)=p$ o $q$ $B$ ahora puede utilizar el Algoritmo de Euclides para encontrar a uno de los números primos).
Nota: una desventaja de este método es que el $B$ puede "hacer trampa" en la que él puede pretender perder. Es decir, se puede decir que el $A$ acertó incluso si ella no lo hacía. Este defecto no parecen significar mucho en su instancia (por lo general es seguro asumir que ambas partes están realmente tratando de ganar).
