Right, a primality test is not hard like factorisation, but it's harder than multiplication. Our pebblesorters are clearly somewhere between multiplication and prime testing. If a pebblesorter proved something like the AKS algorithm, they would win more than the Gödel prize!