el test de primalidad de Fermat,
question: ¿Cuál es un caso sencillo de una prueba probabilística?, context: Un ejemplo particularmente simple de una prueba probabilística es el test de primalidad de Fermat, que se basa en el hecho de que np ≡ n (mod p) para cualquier n si p es un número primo. Si tenemos un número b que queremos probar para la primalidad, entonces trabajamos nb (mod b) para un valor aleatorio de n como prueba. Un defecto de esta prueba es que hay algunos números compuestos (los números de Carmichael) que satisfacen la identidad de Fermat a pesar de que no son primos, por lo que la prueba no tiene forma de distinguir entre números primos. Los números de Carmichael son sustancialmente más raros que los números primos, por lo que esta prueba puede ser útil para propósitos prácticos. Extensiones más potentes de la prueba de primalidad de Fermat, como las pruebas de Baillie-PSW, Miller-Rabin, y Solovay-Strassen, están garantizadas en algún momento cuando se aplican a un número compuesto.
¿Cuál es un caso sencillo de una prueba probabilística?
Un ejemplo particularmente simple de una prueba probabilística es el test de primalidad de Fermat, que se basa en el hecho de
Un ejemplo particularmente simple de una prueba probabilística es el test de primalidad de Fermat, que se basa en el hecho de que np ≡ n (mod p) para cualquier n si p es un número primo. Si tenemos un número b que queremos probar para la primalidad, entonces trabajamos nb (mod b) para un valor aleatorio de n como prueba. Un defecto de esta prueba es que hay algunos números compuestos (los números de Carmichael) que satisfacen la identidad de Fermat a pesar de que no son primos, por lo que la prueba no tiene forma de distinguir entre números primos. Los números de Carmichael son sustancialmente más raros que los números primos, por lo que esta prueba puede ser útil para propósitos prácticos. Extensiones más potentes de la prueba de primalidad de Fermat, como las pruebas de Baillie-PSW, Miller-Rabin, y Solovay-Strassen, están garantizadas en algún momento cuando se aplican a un número compuesto.
Un ejemplo particularmente simple de una prueba probabilística es <hl> el test de primalidad de Fermat, <hl> que se basa en el hecho de
Un ejemplo particularmente simple de una prueba probabilística es <hl> el test de primalidad de Fermat, <hl> que se basa en el hecho de que np ≡ n (mod p) para cualquier n si p es un número primo. Si tenemos un número b que queremos probar para la primalidad, entonces trabajamos nb (mod b) para un valor aleatorio de n como prueba. Un defecto de esta prueba es que hay algunos números compuestos (los números de Carmichael) que satisfacen la identidad de Fermat a pesar de que no son primos, por lo que la prueba no tiene forma de distinguir entre números primos. Los números de Carmichael son sustancialmente más raros que los números primos, por lo que esta prueba puede ser útil para propósitos prácticos. Extensiones más potentes de la prueba de primalidad de Fermat, como las pruebas de Baillie-PSW, Miller-Rabin, y Solovay-Strassen, están garantizadas en algún momento cuando se aplican a un número compuesto.
<hl> Un ejemplo particularmente simple de una prueba probabilística es el test de primalidad de Fermat, que se basa en el hecho de <hl> que np ≡ n (mod p) para cualquier n si p es un número primo. Si tenemos un número b que queremos probar para la primalidad, entonces trabajamos nb (mod b) para un valor aleatorio de n como prueba. Un defecto de esta prueba es que hay algunos números compuestos (los números de Carmichael) que satisfacen la identidad de Fermat a pesar de que no son primos, por lo que la prueba no tiene forma de distinguir entre números primos. Los números de Carmichael son sustancialmente más raros que los números primos, por lo que esta prueba puede ser útil para propósitos prácticos. Extensiones más potentes de la prueba de primalidad de Fermat, como las pruebas de Baillie-PSW, Miller-Rabin, y Solovay-Strassen, están garantizadas en algún momento cuando se aplican a un número compuesto.