(algassert.com)

335 points ingve | 2 comments | 31 Aug 25 12:14 UTC | HN request time: 0.022s | source

1. djha-skin ◴[31 Aug 25 22:24 UTC] No.45087650[source]▶

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

replies(1): >>45087867 #

2. cvoss ◴[31 Aug 25 23:02 UTC] No.45087867[source]▶

>>45087650 (TP) #

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.

↑

Why haven't quantum computers factored 21 yet?