```#!/usr/local/bin/python3

# An implementation of the Goldwasser-Micali encryption algorithm which transmits a quadratic
# residue for a 0 bit and a quadratic non-residue for a 1 bit. The cipertext is one integer
# for each plaintext bit.

from sympy import isprime, randprime
from random import randint

def text_to_bits(text):
bits = bin(int.from_bytes(text.encode(), 'big'))[2:]

return list(map(int, bits.zfill(8 * ((len(bits) + 7) // 8))))

def bits_to_text(bits):
n = int(''.join(map(str, bits)), 2)

return n.to_bytes((n.bit_length() + 7) // 8, 'big').decode()

def legendre(a, p):
assert(p != 2 and isprime(p))
if a % p == 0:
l = 0
else:
l = pow(a, (p - 1) // 2, p)
if l == p - 1:
l = -1

return l

def test_bit(b, p, q):
result = 1
if legendre(b, p) == 1 and legendre(b, q) == 1:
result = 0

return result

def encrypt(n, z, b):
e = pow(randint(1, n), 2, n)
if b == 1:
e = (e * z) % n

return e

n_max = 10000000

p = randprime(1, n_max)
print('p = {0:d}'.format(p))

# Don't want n to be p squared. Too easy to factor.
while True:
q = randprime(1, n_max)
if p != q:
break;

print('q = {0:d}'.format(q))

# Give choice of z some room to breathe by starting "small"
z = (p - 1) // 2
while True:
if legendre(z, p) == -1 and legendre(z, q) == -1:
break
z += 1

print('z = {0:d}'.format(z))

n = p * q
print('n = p * q = {0:d}'.format(n))

pt = '''Whose woods these are I think I know.
His house is in the village, though;'''
print('\nPlaintext before:')
print(pt)
digs = text_to_bits(pt)

es = [encrypt(n, z, b) for b in digs]
print('\nCiphertext:')
print(es)

digs_after = [test_bit(e, p, q) for e in es]
print('\nDeencrypted ciphertext:')
print(bits_to_text(digs_after))

# Sample Output:

# p = 1203193
# q = 6717713
# z = 601599
# n = p * q = 8082705257609

# Plaintext before:
# Whose woods these are I think I know.
# His house is in the village, though;

# Ciphertext:
#[1292575848261, 5839775397279, 5554308066094, 330297141326, 7512773820554,
# ...
# 4397218752399, 5621202712249]

# Deencrypted ciphertext:
# Whose woods these are I think I know.
# His house is in the village, though;
```