Python Rabin-Miller Algoritması İle Asallık Testi

#Bu yazıyı çeviri olarak yazıyorum, kod kaynağı aşağıdaki sitede bir kitapta yer alıyor.
#Birkaç satırı gerektiği için ekledim.
from __future__ import print_function
# Rabin-Miller Algoritması İle Asallık Testi.
# http://inventwithpython.com/hacking (BSD Licensed)

import random

def rabinMiller(num):
    #Sayımız eğer asalsa True döner
    s=num-1
    t=0
    while s%2==0:
        s=s//2 # s bitene kadar yarısını alacağız.
        t +=1  # t'yi tutma nedeni ise s'nin kaç kere 2'ye bölünüdüğünü tutmak istememizdir.

    for trials in range(5): #num değerinin asallığını 5 defa yanlışlamaya çalışacağız.
        a=random.randrange(2,num-1)
        v=pow(a,s,num)
        if v!=1: # v, 1'e eşitse çalışmayacak
            i=0
            while v !=(num-1):
                if i==t-1:
                    return False
                else:
                    i=i+1
                    v=(v**2)%num
    return True

def isPrime(num):
    #sayı asal ise True döner.rabinMiller() çağrılmadan önce daha hızlı asal sayı test eder.
    if num<2:
        return False
        # 0,1 ve negatif sayılar asal sayılara dahil değiller.

    # num sayısının asallığını ilk birkaç düzine asal sayıya bölerek zamanın 1/3 ü gibi kısa bir sürede karar verebilir.
    # Bu rabinMiller() den daha hızlıdır.Ama rabinMiller() gibi sayının asallığının ispatını garantileyemez.
    lowPrimes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
    if num in lowPrimes:
        return True

    # Herhangi bir lowPrimes elemanlarının num ile bölünemeyeceğini görelim.
    for prime in lowPrimes:
        if (num%prime==0):
            return False

    #Bu fonksiyon asal sayıyı doğrulayamadıysa rabinMiller() fonksiyonunu çağırıyoruz.
    return rabinMiller(num)

def generateRabinMiller(keysize=1024):
    #keysize bitleri boyutuyla rasgele bir asal sayı döndürün.
    while True:
        num=random.randrange(2**(keysize-1),2**(keysize))
        if isPrime(num):
            return num
#isPrime() fonksiyonunu dene.
#print(isPrime(19))

#rabinMiller()'i dene

print(rabinMiller(15)==True and "Prime" or "\tNot Prime\t",end="Work is end.I'm going to my bed.\n")

#Gördüğünüz gibi print() içine şart ifadesi yazıp kontrolünü yukarıdaki
#fonksiyonların içeriğini değiştirmeden yaptık.


Comments

Post a Comment

Popular posts from this blog

Tech Duos For Web Development

Complete Guide to Web Development Technology Stacks Complete Guide to Web Development Technology Stacks Choosing the Right Technology Stack Selecting the appropriate technology stack is one of the most critical decisions in web development. Your choice impacts: Development speed - How quickly you can build and iterate Scalability - How well your application can grow Performance - The speed and responsiveness of your app Maintainability - How easy it is to update and extend your code Team expertise - The skills your developers need to have Cost - Both development and hosting expenses Pro Tip: Consider your project requirements, team skills, and long-term maintenance needs when choosing a stack. Popular Technology Stacks MERN Stack The MERN stack is one of the most po...
Read more

CIFAR-10 Dataset Classification Using Convolutional Neural Networks (CNNs) With PyTorch

CIFAR-10 Image Classification with CNN (PyTorch) - Complete Guide CIFAR-10 Image Classification Using CNN with PyTorch This comprehensive guide demonstrates how to classify images from the CIFAR-10 dataset using Convolutional Neural Networks (CNNs) built with PyTorch. The project covers the entire machine learning pipeline from data loading to model deployment, including advanced techniques for improving performance. 🚀 Key Features Complete PyTorch implementation Data augmentation techniques Multiple CNN architectures Training visualization Model evaluation metrics Hyperparameter tuning Model saving/loading Deployment options 📊 Performance Baseline model: ~70% accuracy Improved mod...
Read more

Long-short-term-memory (LSTM) Word Prediction With PyTorch

LSTM Text Generation with PyTorch - Complete Guide LSTM Text Generation with PyTorch A comprehensive guide to building word-level language models with Long Short-Term Memory networks Introduction to LSTM Text Generation Long Short-Term Memory (LSTM) networks are a special kind of recurrent neural network (RNN) capable of learning long-term dependencies. They are particularly useful for sequence prediction problems like text generation, where the context from previous words is crucial for predicting the next word. Key Concepts Word-level modeling : Predicts the next word given previous words Embeddings : Dense vector representations of words ...
Read more