Sequential squaring ⇒ FAC
Statement
If sequential squaring holds for with some gap , then factoring the moduli that outputs is hard, since the factors of give and with it in time — RSW96.
Sketch
Given , run the factoring algorithm on ; on a factor , set , compute with multiplications, and output , which equals because . The factoring algorithm has polynomial size, hence depth at most some polynomial , and the rest has depth ; for every polynomial with above this total, the adversary has depth at most and succeeds whenever factoring does.
Notes
- The converse holds for generic-ring algorithms (FAC ⇒ Sequential squaring (generic ring model)) — RS20b.