6.gyakorlat

RöpZH

Melyik állítás hamis?

• egy modulo m maradékosztály egymást követő elemei között a távolság m
• minden x és minden nemnulla m egészre igaz hogy: x eleme x mod m maradékosztály
• a kongruencia reláció antiszimmetrikus
• a kongruencia reláció reflexív

Írjon foo() néven függvényt, amely paraméterként egy pozitív egész számot fogad, és visszatér azon 1-nél nagyobb, de a paraméternél kisebb számok listájával, amelyek relatív prímek a paraméterhez.

def foo(R):

L=[]

for i in [1..R]: # range(2,R) # [2..(R-1)]

if gcd(i, R) == 1 and i!=1 and i !=R:

L.append(i)

return L

1. feladat

Írjon RNS_ConvertTo() néven függvényt, amely paraméterként a modulusok listáját valamit egy pozitív egész számot kap, és visszatér a szám moduláris számábrázolásbeli alakjával (azaz a reprezentánsok (residues) listájával), ahol a használt modulusok (moduli) a paraméterként kapott modulusok listája legyen.

Amennyiben a kapott egész szám nem ábrázolható a kapott modulusok által meghatározott intervallumban, akkor a függvény dobjon ValueError kivételt.

def RNS_ConvertTo(moduli, a):

M = prod(moduli)

if a >= M:

raise ValueError("RNS_ConvertTo() error: " + str(a) + " cannot be represented with moduli " + str(moduli))

return [a % moduli[i] for i in [0..len(moduli) - 1]]

mods = [2,3,5,7]

RNS_ConvertTo(mods, 16) # 16 mod 7, 16 mod 11, 16 mod 15 # % operátor a maradékképzés

RNS_ConvertTo(mods, 52)

RNS_ConvertTo(mods, 200)

#RNS_ConvertTo(mods, 2000)

RNS_ConvertTo(mods,143)

RNS_ConvertTo(mods,11)

[0, 1, 1, 2][0, 1, 2, 3] [0, 2, 0, 4][1, 2, 3, 3] [1, 2, 1, 4]

[2, 5, 1] [3, 8, 7] [4, 2, 5] Error in lines 10-10

Traceback (most recent call last):

File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1230, in execute

exec(

File "", line 1, in

File "", line 4, in RNS_ConvertTo

ValueError: RNS_ConvertTo() error: 2000 cannot be represented with moduli [7, 11, 15]

2. feladat

Írjon RNS_add(), RNS_sub() és RNS_mul() néven függvényeket, amelyek paraméterként a modulusok listáját valamit két darab moduláris számábrázolásbeli egész számot kapnak, és térjenek vissza a megfelelő művelet végeredményével.

A függvények nem megfelelő paraméterek esetén dobjanak ValueError kivételt.

def RNS_add(moduli, a, b):

if not(len(moduli) == len(a) and len(a) == len(b)):

raise ValueError("RNS_add() error: invalid arguments")

return [(a[i] + b[i]) % moduli[i] for i in [0..len(moduli)-1]]

def RNS_sub(moduli, a, b):

if not(len(moduli) == len(a) and len(a) == len(b)):

raise ValueError("RNS_sub() error: invalid arguments")

return [(a[i] - b[i]) % moduli[i] for i in [0..len(moduli)-1]]

def RNS_mul(moduli, a, b):

if not(len(moduli) == len(a) and len(a) == len(b)):

raise ValueError("RNS_mul() error: invalid arguments")

return [(a[i] * b[i]) % moduli[i] for i in [0..len(moduli)-1]]

def RNS_div(moduli, a, b):

if not(len(moduli) == len(a) and len(a) == len(b)):

raise ValueError("RNS_div() error: invalid arguments")

try:

return [(a[i] / b[i]) % moduli[i] for i in [0..len(moduli)-1]]

except ZeroDivisionError:

print('RNS_div() error: cannot divide by zero')

res = RNS_add(mods, [2, 5, 1], [3, 8, 7])

print(res)

#RNS_add(mods, [2, 5, 1], [3, 8])

RNS_sub(mods, [3, 8, 7], [2, 5, 1])

RNS_mul(mods, [2, 5, 1], [3, 8, 7])

RNS_div(mods,[1, 2, 3, 3],[1, 2, 1, 4])

# [1, 1, 3, 6]

3. feladat

Írjon RNS_ConvertFrom() néven függvényt, amely paraméterként a modulusok listáját valamit egy moduláris számábrázolással megadott számot fogad, és térjen vissza a szám 10-es számrendszerbeli alakjával.

A függvény nem megfelelő paraméter esetén dobjon ValueError kivételt.

CRT([5, 2, 8], [7, 11, 15])

# 68

def RNS_ConvertFrom(moduli, a):

if len(moduli) != len(a):

raise ValueError("RNS_ConvertFrom(): invalid arguments")

return CRT(a, moduli)

print(mods)

print(res)

RNS_ConvertFrom(mods, res)

# [7,11,15]

4. feladat

Végezze el az 5. feladatsor 4. feladatát az általunk implementált függvényekkel.

5. feladat

Végezze el a 200000000000000000000000000 + 450000000000000000000000011 összeadást moduláris számábrázolással.

# 200000000000000000000000000 + 450000000000000000000000011

mods2 = [300000, 300007, 300017, 300023, 300043]

# next_prime(300000)

gcd([300000, 300002])

RNS_ConvertTo(mods2, 200000000000000000000000000)

RNS_ConvertTo(mods2, 450000000000000000000000011)

#RNS_ConvertTo(mods2, 200000000000000000000000000 + 450000000000000000000000011)

RNS_add(mods2, [200000, 264055, 126363, 120927, 123279], [11, 219126, 59315, 197091, 202378])

RNS_ConvertFrom(mods2, [200011, 183174, 185678, 17995, 25614])