ŚLEPA ULICZKA OKAZAŁA MIEĆ WYJŚCIE !!!
Test Millera-Rabina BEZ RANDOMU, BEZ LOSOWOŚCI !!!
CZY CHCESZ SIĘ O TYM DOWIEDZIEĆ ?
CZTERY NIEZALEŻNE WERSJE PROGRAMU BEZ RANDOMU.!!!
NOWY FILMIK:
Test Pierwszeństwa Mart'a (Miller-Rabin/BEZ RANDOMU)
Wystarczy zmienić (a)
a = random.randint(2, L – 2) Tutaj mamy nasze (a)
Gdybym ci powiedział,że: Liczby Pierwsze, to różnica dwóch Określonych Kwadratów S -M=L.
Film:PRAWO CIĄGU LICZB NIEPARZYSTYCH
Tylko weź znajdź te kwadraty przed samym L, znowu trzeba szukać
Test Paraboliczny, nie jestem matematykiem nie Pytaj mnie co to znaczy He He:
import math
import random
import time
import sys
# Zwiększenie limitu dla dużych liczb (np. 50000 cyfr)
sys.set_int_max_str_digits(50000)
def miller_rabin(n, k=5): # Test Millera-Rabina z k powtórzeniami
if n < 2:
return False
if n in (2, 3):
return True
if n % 2 == 0:
return False
# Rozkład n-1 na d * 2^r
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n) # a^d % n
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def test_pierwiastka_paraboliczna(x, czas_limit=2):
zero_count = 0
zero_indices = [] # Lista przechowująca znalezione wartości n
start_time = time.time()
print(f"Wartość x: {x}")
print("L = w^2 - n^2")
for a in range(1, int(math.isqrt(x)) + 1):
if time.time() - start_time > czas_limit:
if miller_rabin(x): # Jeśli czas minął, sprawdzamy testem M-R
print(f"{x} | Pierwsza | Zerowe miejsca: 1")
return True
else:
print(f"{x} | Złożona | Zerowe miejsca: >=2")
return False
if x % a == 0: # Znaleziono dzielnik a
b = x // a # Drugi dzielnik b
if (a + b) % 2 == 0 and (b - a) % 2 == 0:
w = (a + b) // 2 # Obliczenie w
n = (b - a) // 2 # Obliczenie n
# Obliczenie w i n z równań
w = math.isqrt(L + n**2) # Poprawna definicja w
n = math.isqrt(w**2 - L) # Poprawna definicja n
print(f"a = {a}, b = {b}, w = {w}, n = {n}")
zero_count += 1
zero_indices.append(n)
if zero_count >= 2:
print(f"Liczba {x} jest złożona (liczba miejsc zerowych >= 2)")
return False # Liczba jest złożona
return True # Jeśli znaleziono tylko jedno miejsce zerowe, liczba jest pierwsza
print("#### Test Pierwszeństwa Mart'a (Paraboliczny)")
# Pytamy użytkownika o liczbę
L = int(input("Podaj liczbę do sprawdzenia: "))
# Wywołujemy funkcję i sprawdzamy wynik
wynik = test_pierwiastka_paraboliczna(L)
if wynik is None:
print(f"{L}: Nie udało się określić (przekroczony czas)")
elif wynik:
print(f"{L}: Liczba jest pierwsza")
else:
print(f"{L}: Liczba jest złożona")
Test pierwszeństwa z filtrem Binarnym, w zasadzie krótką mam pamięć, już prawie o nim zapomniałem :
import random
import sys
# Zwiększenie limitu dla dużych liczb (np. 50000 cyfr)
sys.set_int_max_str_digits(50000)
def is_symmetric_binary(n):
"""Sprawdza, czy liczba binarna jest symetryczna."""
binary_str = n
return binary_str == binary_str[::-1] # Sprawdzenie symetrii
def has_central_one(binary_str):
"""Sprawdza, czy centralny bit (lub bity) liczby symetrycznej to 1."""
length = len(binary_str)
if length % 2 == 1: # Liczba o nieparzystej długości
return binary_str[length // 2] == '1'
else: # Liczba o parzystej długości
central_bits = binary_str[length // 2 - 1:length // 2 + 1]
return '1' in central_bits
def is_even(binary_str):
"""Sprawdza, czy liczba binarna jest parzysta (ostatni bit = 0)."""
return binary_str[-1] == '0'
def is_divisible_by_3_or_5(binary_str):
"""Sprawdza, czy liczba binarna jest podzielna przez 3 lub 5."""
n = int(binary_str, 2)
return (n % 3 == 0 or n % 5 == 0) and n not in {3, 5}
def is_divisible_by_small_primes(binary_str):
"""Sprawdza, czy liczba binarna jest podzielna przez małe liczby pierwsze (np. 2, 3, 5, 7, 11)."""
n = int(binary_str, 2)
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
for prime in small_primes:
if n % prime == 0 and n != prime:
return True # Liczba jest podzielna przez małą liczbę pierwszą
return False
def miller_rabin_test(binary_str, k=5):
"""
Test Millera-Rabina do sprawdzania pierwszości (przy użyciu binarnego zapisu liczby).
"""
n = int(binary_str, 2)
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0:
return False
# Rozkład n-1 na d * 2^r
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# Główny test
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def has_repeating_blocks(binary_str):
"""Sprawdza, czy liczba binarna ma powtarzające się bloki."""
length = len(binary_str)
for i in range(1, length // 2 + 1):
# Sprawdza, czy początkowy fragment długości i powtarza się
if length % i == 0 and binary_str[:i] * (length // i) == binary_str:
return True
return False
def is_repunit(binary_str):
"""Sprawdza, czy liczba binarna jest liczbą repunitową (składa się z jedynek)."""
return binary_str == '1' * len(binary_str)
def is_prime_repunit(binary_str):
"""Sprawdza, czy liczba repunitowa jest liczbą pierwszą."""
n = int(binary_str, 2)
# Liczba repunitowa jest liczbą pierwszą tylko wtedy, gdy jest postaci 2^p - 1, gdzie p jest liczbą pierwszą.
p = len(binary_str) # długość ciągu jedynek to p
if (2 ** p - 1) == n:
return miller_rabin_test(binary_str)
return False
def binary_filter_with_primality_check(binary_str):
"""
Filtruje liczbę binarną na podstawie reguł i przeprowadza test Millera-Rabina dla potencjalnie pierwszych.
Zwraca True, jeśli liczba jest pierwsza.
"""
fermat_primes = {3, 5, 17, 257, 65537} # Znane liczby Fermata
n = int(binary_str, 2) # Zamiana na dziesiętną, by sprawdzić w zbiorze Fermata
if n in fermat_primes:
return True # Liczba Fermata jest pierwsza
if is_even(binary_str) and n != 2:
return False # Wszystkie liczby parzyste, oprócz 2, są złożone
if is_divisible_by_3_or_5(binary_str):
return False # Liczby podzielne przez 3 lub 5 są złożone
if is_divisible_by_small_primes(binary_str):
return False # Liczba jest podzielna przez małe liczby pierwsze
# Sprawdzamy liczby repunitowe
if is_repunit(binary_str):
return is_prime_repunit(binary_str)
# Filtrujemy liczby z powtarzającymi się blokami
if has_repeating_blocks(binary_str):
return False # Liczba z powtarzającymi się blokami jest złożona
# Filtrujemy liczbę symetryczną z centralnym bitem 1
if is_symmetric_binary(binary_str):
if has_central_one(binary_str):
return miller_rabin_test(binary_str) # Sprawdzamy pierwszość przy pomocy testu Millera-Rabina
else:
return False # Symetryczna liczba z centralnym bitem ≠ 1 jest złożona
# Sprawdzamy potencjalnie pierwsze za pomocą testu Millera-Rabina
return miller_rabin_test(binary_str)
def check_numbers_in_range(x, count):
"""Sprawdza zakres liczb od x po kolei i wypisuje tylko liczby pierwsze."""
print(f"Liczby pierwsze w zakresie od {x} do {x + count - 1}:")
for i in range(x, x + count):
binary_str = bin(i)[2:] # Zamiana na zapis binarny
if binary_filter_with_primality_check(binary_str):
print(i)
# Główna funkcja programu
print("Mart, Test Pierwszeństwa/Filtr Binarny/MAYBY!!!")
if __name__ == "__main__":
try:
x = int(input("Podaj liczbę początkową (x): "))
count = int(input("Podaj ilość kolejnych liczb do sprawdzenia: "))
print()
check_numbers_in_range(x, count)
except ValueError as e:
print(f"Błąd: {e}. Wprowadź poprawne liczby.")
Ostatni jak zmieszczę test NWD:
import math
import random
import sys
# Zwiększenie limitu dla dużych liczb (np. 50000 cyfr)
sys.set_int_max_str_digits(50000)
def suma_podstaw_kwadratow(L):
S = 0
while L > 0:
x = math.isqrt(L) # Największa możliwa podstawa kwadratu
S += x
L -= x * x # Odejmujemy jego kwadrat
return S
def nwd(L, k=5):
if L < 2:
return False
if L in (2, 3):
return True
if L % 2 == 0:
return False
# Rozkład L-1 na d * 2^r
r, d = 0, L - 1
while d % 2 == 0:
r += 1
d //= 2
for _ in range(k):
a = random.randint(2, L - 2)
x = pow(a, d, L) # a^d % L
if x == 1 or x == L - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, L)
if x == L - 1:
break
else:
return False
return True
def znajdz_nwd(L):
S = suma_podstaw_kwadratow(L)
W = math.isqrt(L) # Pierwiastek całkowity z L
max_i = math.floor(math.log2(S*W)) + math.floor(math.log2(L))
najlepszy_dzielnik = math.pi # Początkowa wartość dla największego dzielnika
for i in range(0, max_i + 1): # i od 1 do W
N = L - (W - i) ** 2 # Wyznaczamy N
if N <= 0:
continue # Pomijamy wartości ujemne lub zerowe
gcd1 = math.gcd(L, N) # NWD(L, N)
gcd2 = math.gcd(L, (W - i)) # NWD(L, (W - i)²)
## Prawidłowy warunek
if W**2 == L:
print(f"Liczba badana L = {L} Kwadratowa, dzielnik = {W}")
return "DZIELNIK > 1 LICZBA ZŁOŻONA"
if L%3 == 0:
print(f"Liczba badana L = {L} Złozona, dzielnik = 3")
return "DZIELNIK > 1 LICZBA ZŁOŻONA"
if W**2 == L:
print(f"Liczba badana L = {L} Kwadratowa, dzielnik = {W}")
return "DZIELNIK > 1 LICZBA ZŁOŻONA"
if L%3 == 0:
print(f"Liczba badana L = {L} Złozona, dzielnik = 3")
return "DZIELNIK > 1 LICZBA ZŁOŻONA"
if najlepszy_dzielnik > math.pi or gcd1 > math.pi and gcd2 > math.pi and gcd1 < L and gcd2 < L:
najlepszy_dzielnik = max(najlepszy_dzielnik, gcd1, gcd2)
print(f"Liczba badana L = {L}")
print(f"Największy znaleziony dzielnik: {najlepszy_dzielnik}")
print(f"Maks-dzielnik: {max(gcd1,gcd2)}")
return "DZIELNIK == Liczba naturalna LICZBA ZŁOŻONA"
if najlepszy_dzielnik == math.pi and max(gcd1,gcd2) == 1 and max(gcd1,gcd2) <= math.pi:
print(f"Liczba badana L = {L}")
print(f"Największy znaleziony dzielnik: {najlepszy_dzielnik}")
print(f"Maks-dzielnik: {max(gcd1,gcd2)}")
return "DZIELNIK == math.pi LICZBA PIERWSZA"
# Jeśli nie znaleziono dzielnika => liczba pierwsza
return "DZIELNIK = 1 (LICZBA PIERWSZA)"
def test_prime(L):
# Najpierw testujemy za pomocą funkcji NWD, by sprawdzić, czy liczba jest złożona
nwd_result = znajdz_nwd(L)
if "LICZBA ZŁOŻONA" in nwd_result:
print(f"Na podstawie NWD: {nwd_result}")
return nwd_result
# Jeśli test NWD mówi, że liczba jest pierwsza, wykonujemy test Miller-Rabin
mr_result = nwd(L)
if mr_result:
print("Na podstawie testu Miller-Rabin: LICZBA PIERWSZA")
return "LICZBA PIERWSZA"
else:
print("Na podstawie testu Miller-Rabin: LICZBA ZŁOŻONA")
return "LICZBA ZŁOŻONA"
print("#### Test Pierwszeństwa Mart'a (NWD/Miller-Rabin Test) ####")
# Pytamy użytkownika o liczbę
L = int(input("Podaj liczbę do sprawdzenia: "))
wynik = test_prime(L)
print("Wynik:", wynik)
Tyle, znaczy więcej nie zmieszczę jak Ktoś chce niech się nimi pobawi.Miłego dnia. 
