BFFV
commented
2 years ago Hola!
Si dado un b_i sacado al azar revisas que sea congruente a -1 y también a 1, eso te asegura que si el número n era PRIMO se podrá detectar sin error (como tú dices, ya que los primos siempre darán 1 o -1). El problema es que si te llega un número n COMPUESTO y haces eso, puede perfectamente pasar que te dé 1 para el b_i elegido (por lo que te equivocas retornando que es PRIMO cuando era COMPUESTO), y en ese caso realmente no tienes idea de la probabilidad de error, dado que lo demostrado en las slides (usando el Teorema Chino del Resto) sólo es válido si es que era congruente a -1. Es decir, la única forma de asegurar el error de 1/2 es solamente revisando si es congruente a -1 específicamente (sacrificando el error 0 en caso de que nsea PRIMO para poder abarcar mejor el caso COMPUESTO y tener una cota de error válida).
Espero se entienda, y suerte en el examen!
Hola! tengo una duda sobre el error del test de primalidad verison 3. Dice en las slides que se equivoca retornando compuesto cuando es primo con 1/2 de error.
Lo que entendí de eso es que es porque en el if que revisa el neg es solo si es congruente a -1 y despues pasa directo a chequear si no es congruente a 1 y de ahi sigue , y si b fuera congruente a 1 también sería primo pero no lo chequea entonces ese es el error que habría ya que aunque sea primo neg sería 0.
Está bien interpretarlo asi? Que no me queda tan claro por que no esta chequeando si tambien es congruente a 1. No está equivocandose a proposito entonces? O ese error viene de otra parte?
Gracias!