atlas_q.quantum_hybrid_system.PeriodFinder#
- class atlas_q.quantum_hybrid_system.PeriodFinder[source]#
Bases:
objectCollection of O(√r) period-finding algorithms
Methods
baby_step_giant_step(a, N[, m])Baby-step giant-step algorithm Complexity: O(√r) time and space
collision_detection(a, N[, num_samples])Birthday paradox collision detection Complexity: O(√r) expected
parallel_candidate_search(a, N[, max_candidates])Generate smart candidates and check them In real implementation, this would be GPU-parallelized
pollards_rho(a, N[, max_iter])Floyd's cycle detection algorithm Complexity: O(√r) average case
smart_factorization(a, N)Check if period has small factors Complexity: O(k) where k is number of candidates
- __init__(*args, **kwargs)#
Methods
__init__(*args, **kwargs)baby_step_giant_step(a, N[, m])Baby-step giant-step algorithm Complexity: O(√r) time and space
collision_detection(a, N[, num_samples])Birthday paradox collision detection Complexity: O(√r) expected
parallel_candidate_search(a, N[, max_candidates])Generate smart candidates and check them In real implementation, this would be GPU-parallelized
pollards_rho(a, N[, max_iter])Floyd's cycle detection algorithm Complexity: O(√r) average case
smart_factorization(a, N)Check if period has small factors Complexity: O(k) where k is number of candidates
- static smart_factorization(a, N)[source]#
Check if period has small factors Complexity: O(k) where k is number of candidates
- static pollards_rho(a, N, max_iter=100000)[source]#
Floyd’s cycle detection algorithm Complexity: O(√r) average case
Uses tortoise and hare to detect cycles in sequence: 1, a mod N, a² mod N, a³ mod N, …
- static collision_detection(a, N, num_samples=None)[source]#
Birthday paradox collision detection Complexity: O(√r) expected
Sample random points, find collision f(x₁) = f(x₂) Then period divides |x₁ - x₂|