View Single Post
Old 2019-02-24, 00:16   #30
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26018 Posts
Default Foolproof on TF (5 sigma)

Quote:
Originally Posted by LaurV View Post
Email verification should work (well.. at least, as you said, slow down some badass kids).
Quote:
Originally Posted by Madpoo View Post
If it were asymmetrical so the server could quickly verify, that'd be okay. One glitch is that there are users who genuinely submit a LOT of results daily (think TJAOI or even the Gpu72 bot) so it might place an undue burden on them.
Obviously the hard part is that for no factor (what is the common) there is nothing to check in the usual codes.

In the past I've thought that it is just impossible,
don't have an exact idea what would be the slowdown on gpu (I'd say that less than 1%),
but the check on the server would be terrible fast and close to impossible to fool it:

Let x mod N the unique mod N residue in [0,N).

and H=hash(p,q,t)=(2^p mod q) mod (2^t)

we are expecting to see H=1 for cnt/p/2^(t+1) different q primes (q=1,7 mod 8) if there are cnt primes in [2^b,2^(b+1)). Save these q numbers if q is prime ( or pseudoprime ) and send them to the server at the end of the computation.

The number of hits follows a binomial distribution with:
Binom(N,r)=Binom(cnt/2/p,1/2^t)

Code:
where:
N=cnt/(2*p)
r=1/2^t
ev=N*r (the expected value)
sigma=sqrt(N*r*(1-r))
here mark the submission as suspect if you'd see less than ev-5*sigma different(!) q values from the [2^b,2^(b+1)) interval, where q mod 8={1,7} and q is prime (or pseudoprime, that would change almost nothing). Ofcourse accept the submission for p, if it has found at least one q>1 divisor of mp (because it is possible that in this case the search used an early abort strategy at success, what is common).

choose such t for that say 1000<ev<2000 (there'll be a unique t if N>1000, and if the range is not very small).


ps. For large bounds we have exact prime counts for [2^b,2^(b+1)), but you can also use estimations. Don't count composite q values, because that mess up these things, depends on your sieving bound etc.
Why would be hard to fool it? Because for actual q prime divisors of mp we have also H=1, if you could find these q much faster, than the whole tf would be also much faster.

Last fiddled with by R. Gerbicz on 2019-02-24 at 00:19 Reason: typo
R. Gerbicz is offline   Reply With Quote