Remix.run Logo
djha-skin 6 days ago

Does this essentially mean that the Big-O "circuitry requirements" of factoring integers using Schorr's is super polynomial?

cvoss 6 days ago | parent [-]

The article explains the gate cost mostly comes from O(n) multiply-under-mod ops on O(n)-bit numbers. Each op could be naively spelled out as O(n^2) gates. So the whole thing looks cubic to me at worst.