mdomans/pyRNS — Issue #1: Modules
Author: ch3sh1r
Created: 2011-12-17 17:11:16+00:00
State: open

At RNS we have a field modulo M = m_1 * m_2 * ... * M_n. On this, as i see, there is no need to tow all the modules found by a sieve of Eratosthenes. Then there should be something like this:

def generate_modules(self, system_limit):
"""Generates modules with system_limit coverage.
"""
numbers = range(3, system_limit, 2)
mroot = system_limit ** 0.5
half = len(numbers)
i = 0
m = 3
while m <= mroot:
if numbers[i]:
j = (m ** 2 - 3) // 2
numbers[j] = 0
while j < half:
numbers[j] = 0
j += m
i += 1
m = 2 * i + 3
coprimes = [x for x in numbers if x]
i = 0
m = 1
while m <= system_limit:
m *= coprimes[i]
i += 1
return coprimes[:i]

Moreover, all these modules do not have to be prime, coprimes is enough.