3 ms·
Does this essentially mean that the Big-O "circuitry requirements" of factoring integers using Schorr's is super polynomial?
by djha-skin 1y ago
Does this essentially mean that the Big-O "circuitry requirements" of factoring integers using Schorr's is super polynomial?
- cvoss 1y agoThe 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.