0

I was trying to write a basic implementation of a deterministic Miller-Rabin test but my limited Python background is getting in the way. It seems that, in the section of the program pasted below, the outer for loop is skipping over every other element after the inner while loop completes. Any ideas as to why this is the case?

for integer in integers:
    print("The current integer is " + str(integer))
    i = 0
    while i < len(powers):
        print(str(integer) + "^" + str(powers[i]) + " + 1 mod N =")
        print((pow(integer,powers[i],N) + 1)%N)     
        if (pow(integer,powers[i],N) + 1)%N == 0:
            integers.remove(integer)
            i += 1
            break
        else:
            i += 1
anon_epsilon
  • 1
  • 1
  • Did you forget to add an indentation after the for loop or did it got removed when you paste it here? – somesingsomsing Apr 06 '17 at 20:40
  • @AquaticallyChallengedFish: Sorry, the indentations were lost after pasting. Fixed. – anon_epsilon Apr 06 '17 at 20:43
  • Your code snippet is not complete. What are the values of `integers`, `powers`, etc.? See [How to create a Minimal, Complete, and Verifiable example](http://stackoverflow.com/help/mcve). – Rory Daulton Apr 06 '17 at 20:45
  • Probably has to do with modifying your iterator mid iteration: `integers.remove(integer)` If this is indeed the case, you could just iterate an index.. – Aaron Apr 06 '17 at 20:45
  • @RoryDaulton it's a miller-rabin primality test... it's quite obvious what they represent – Aaron Apr 06 '17 at 20:46
  • @Aaron: Thanks, that's it. A hacky way to resolve is to create a clone of the list integers and iterate over the clone while removing from the original list. – anon_epsilon Apr 06 '17 at 21:13
  • @Aaron: It's obvious what they *are supposed to* represent. Many bugs are hidden because the programmer makes assumptions about what the current value of a variable is. – Rory Daulton Apr 06 '17 at 22:41

1 Answers1

-5

Put the i += 1 outside the if and else statements

So

for integer in integers:
    print("The current integer is " + str(integer))
    i = 0
    while i < len(powers):
        print(str(integer) + "^" + str(powers[i]) + " + 1 mod N =")
        print((pow(integer,powers[i],N) + 1)%N)     
        if (pow(integer,powers[i],N) + 1)%N == 0:
            integers.remove(integer)

            break
        i += 1
somesingsomsing
  • 3,182
  • 4
  • 29
  • 46