Gibt es eine Funktion "wahrscheinlich teilbar" ?

[Karl-Heinz Hofmann]

Code: Alles auswählen

def test_faktor(exponent,faktor):
    if "faktor ist möglich":                        # hier müsste der Codeschnipsel stehen
        if pow(2,exponent,faktor) == 1:             # letztendlich müsste doch streng getestet werden
            return True
        else: 
            return False
    else:                                           # die eingebaute pow funktion wurde hier nicht gebraucht 
        return False                     

- Die Base von pow ist immer 2
- Der Modulo Rest interessiert nicht
- Der Exponent ist sehr groß und prim
- Der Faktor ist auch sehr groß und vorgesiebt, also nicht sicher prim.
- Der Faktor/Faktoren hat die Form 2k * exponent + 1

Jemand eine Idee ? Gruß Kalli

[Sirius3]

Dieses wahrscheinlich teilbar macht ja genau die Potenz. Statt mit Millionen Bit Zahlen braucht man nur ~100bit Zahlen. Wenn es eine geschicktere Methode gäbe, würde sie der Algorithmus, den du abgeschrieben hast, den auch nutzen.