#!/usr/bin/env python
# coding: utf-8

# # Zahlentheorie
# 
# 
# 

# Python kann von Haus aus mit großen Ganzzahlen (die mehr als 64-Bit haben) umgehen.

# In[1]:


x = 900000000000000000000000000010000000000000000000000001
y = 99985555444433332222111199988866665554444333322221111
x*y


# In[2]:


x % y


# ## Zahlentheorie mit SymPy
# 
# Das Submodul [sympy.ntheory](http://docs.sympy.org/latest/modules/ntheory.html) (engl. "number theory") beinhaltet zahlentheoretiche Funktionen.

# ### Primzahltest

# In[3]:


from sympy.ntheory import isprime, nextprime
isprime(20150407)


# In[4]:


nextprime(20150407)


# Struktur der Primzahlen bis 2000:

# In[5]:


from __future__ import print_function
zeilen, spalten = 25, 80
for z in range(zeilen):
    for s in range(spalten):
        n = (s + 1) + spalten * (z)
        print("o" if isprime(n) else " ", end="")
    print()


# ### Faktorisierung in $\mathbb{Z}$
# 
# Das Ergebnis ist ein `dict`, wobei die Schlüssel die Primzahlen und die Werte die Vielfachheit sind.

# In[6]:


from sympy.ntheory import factorint
factorint(1116130609622197)


# In[7]:


fc2 = factorint(1116130609622197)
fc2


# Check

# In[9]:


z = 1
for primzahl, vielfachheit in fc2.items():
    z *= primzahl**vielfachheit
z


# ### Chinesischer Restsatz

# In[10]:


from sympy.ntheory.modular import crt
crt([2, 3, 13], [1, 2, 7])


# In[11]:


[59 % m for m in [2, 3, 13]]


# ### Partitionen von n

# In[12]:


from sympy.ntheory import npartitions
for i in range(0, 2001, 100):
    np = npartitions(i)
    print("P(%5d) = %d" % (i, np))


# ### Lengendre-Symbol

# In[13]:


from sympy.ntheory.residue_ntheory import legendre_symbol
legendre_symbol(49, 997)


# In[14]:


legendre_symbol(7, 997)


# ### Möbiusfunktion

# In[15]:


from sympy.ntheory import mobius
mobius(11111222227777)


# In[16]:


factorint(11111222227777)


# In[17]:


mobius(11111222227779)


# In[18]:


factorint(11111222227779)


# ## Endliche Körper
# 
# Welche Punkte in $\mathbb{F}_7 \times \mathbb{F}_7$ liegen am Einheitskreis, also erfüllen $x^2 + y^2 = 1$?

# In[19]:


from itertools import product

F7 = range(7)

for x, y in product(F7, F7):
    if (x**2 + y**2) % 7 == 1:
        print("%d:%d" % (x, y))


# *Bemerkung:* Das ist natürlich nicht wirklich $\mathbb{F}_7$, denn wir brauchen die Modulo-Operation.
# Eine gute Aufgabe wäre, eine Klasse für $\mathbb{F}_p$ zu implementieren,
# dessen Elemente (also, man braucht auch eine Klasse für die Elemente) die Basisoperationen beherrschen.