20190524, 01:39  #1 
Apr 2019
5·41 Posts 
Is there an "anti"CRT?
I'm wondering if there's some bizarro backwards way to apply Chinese Remainder Theorem.
If I can prove that a number x is *not* congruent to a specific value (a_{i} mod p_{i}) for many primes p_{i}, is it possible to then determine what x is? Last fiddled with by hansl on 20190524 at 01:40 
20190524, 03:12  #2 
Apr 2019
5×41 Posts 
Hrm, after calculating a little bit, it seems that this is pretty awful concept if I can only tell one incongruence per prime.
I tried calculating product of primes p/(p1), which I think should correspond to the ratio of search space eliminated given 1 incongruence per prime: Code:
? lim=2; prd=1; forprime(p=2,10^14,prd*=p/(p1.);if(prd>=lim,print("Primes up to "p," for "lim". prd="prd);lim++)) Primes up to 2 for 2. prd=2.000000000000000000000000000 Primes up to 3 for 3. prd=3.000000000000000000000000000 Primes up to 7 for 4. prd=4.375000000000000000000000000 Primes up to 13 for 5. prd=5.213541666666666666666666667 Primes up to 23 for 6. prd=6.112910517939814814814814815 Primes up to 43 for 7. prd=7.056197013773996955043805931 Primes up to 79 for 8. prd=8.035259023222138602497561472 Primes up to 149 for 9. prd=9.040126426407024715829558918 Primes up to 257 for 10. prd=10.00371973209101038332513164 Primes up to 461 for 11. prd=11.02092114940689046284052754 Primes up to 821 for 12. prd=12.00090956610939352092225948 Primes up to 1451 for 13. prd=13.00352996444186925072418327 Primes up to 2549 for 14. prd=14.00087838609159858081303106 Primes up to 4483 for 15. prd=15.00298756381295884564016353 Primes up to 7879 for 16. prd=16.00045526127758253537314039 Primes up to 13859 for 17. prd=17.00087696116755234920148492 Primes up to 24247 for 18. prd=18.00045848572046132210667669 Primes up to 42683 for 19. prd=19.00014695308393109105897867 Primes up to 75037 for 20. prd=20.00016074285687209995442682 Primes up to 131707 for 21. prd=21.00008729814628257453224293 Primes up to 230773 for 22. prd=22.00002670928254673774283860 Primes up to 405401 for 23. prd=23.00000769427039541874730901 Primes up to 710569 for 24. prd=24.00002919315092236763807909 Primes up to 1246379 for 25. prd=25.00001613992436832757643451 Primes up to 2185021 for 26. prd=26.00001149432701216229037958 Primes up to 3831913 for 27. prd=27.00000435007185786747062343 Primes up to 6720059 for 28. prd=28.00000251500300820662728034 Primes up to 11781551 for 29. prd=29.00000072535010484630946352 Primes up to 20657677 for 30. prd=30.00000074501229678885932771 Primes up to 36221753 for 31. prd=31.00000005322932957042954777 Primes up to 63503639 for 32. prd=32.00000029441901794943756935 Primes up to 111333529 for 33. prd=33.00000017321456830195036750 Primes up to 195199289 for 34. prd=34.00000012256309038637866570 ... 
20190524, 07:39  #3 
Dec 2012
The Netherlands
1348_{10} Posts 
That sounds like a version of Mastermind!

20190524, 07:48  #4 
Bamboozled!
May 2003
Down not across
9,859 Posts 
I think you have just rediscovered why trial division is generally used only to remove very small primes from a composite before switching to Pollard rho and ECM.
Last fiddled with by xilman on 20190524 at 07:48 Reason: Fix tpo 
20190524, 09:14  #5  
Apr 2019
5·41 Posts 
Quote:
I have been experimenting with algorithms to see if I can tell anything about fermat factors. It is known that for F_{n}, any factors will be of the form k*2^{n+2}+1 So, given some unfactored composite C of F_{n}, C can be factored into C = (k_{1}*2^{n+2}+1)(k_{2}*2^{n+2}+1) which can be expanded and rearranged to: (C1)/2^{n+2} = k_{1}*k_{2}*2^{n+2}+(k_{1}+k_{2}) So, the interesting thing I discovered is that using this equivalence, given any F_{n}, and prime p>2, I have an algorithm that produces exactly one incongruence (mod p) which seems to apply to all k_{i} on that F_{n}. It gives the same result for any variation of input: F_{n}, or combination of its factors(or even a single known factor by itself), or unfactored composites C. Any ideas why this would be so? 

20190524, 21:22  #6 
Apr 2019
5·41 Posts 
Well, anyways, here's the PARI code, it just tries all combinations of j,k (aka k_{1} k_{2}) (mod p), and it turns out there's always one value that can't be used to result in x(mod p)
Code:
findmoduli(n,sh,kv=[])={ my(r, result, nonzero, dummy, x=(n1)>>sh, p, prd=1.); print("x="x); forprime(p=2,100000, r=Mod(x,p); result=vector(p,dummy,0); for(j=0,p1, for(k=j,p1, if(Mod(j*k<<sh+j+k,p)==r,result[j+1]++;result[k+1]++); ); ); nonzero=0; for(x=1,p,if(result[x]==0,print("Mod(",x1","p")"),nonzero++)); prd *= p/nonzero; \\print("\n", pnonzero, "/", p, "(zeroes/p)\tfactor(p)=",factor(p), " prd="prd); \\,"\n", result); /* \\ Check for correctness if k's provided for(j=1,#kv, for(i=0,p1,if(result[i+1]==0 && kv[j]%p==i, print("FAIL: ", kv[j], "%", p, "=", kv[j]%p, "\n", result); return(); )) ); */ ) } findmoduli(2^4096+1,14) \\ for example, gives same results as: findmoduli(190274191361, 14); Anyways could these sets of incongruences be used in any practical way to help narrow the search of k when trying to completely factor Fermat composites? Last fiddled with by hansl on 20190524 at 21:38 
20190524, 22:44  #7 
Apr 2019
5×41 Posts 
Duhh, I realized this incongruent number j paired with any other k always results in itself, so, substituting k=1, j<<sh+j+1==j I simplified the code down to just take the (n+2) exponent as input, and linear complexity with p
Code:
findmoduli(sh)={ my(p); forprime(p=2,100000000, for(j=1,p1, if(Mod(j<<sh+1,p)==0,print("Mod(",j","p")")); ); ) } Ok, simplified again to constant time Code:
findmoduli(sh)={ my(pow2=1/(1<<sh)); forprime(p=3,1000,print(Mod(pow2,p))); } But since this modular inverse will never result in 0, the incongruence holds regardless if you even check Fn (mod p)==0. Man, what a way to overcomplicate things... Last fiddled with by hansl on 20190524 at 22:53 
20190526, 00:35  #8 
Apr 2019
5×41 Posts 
Just realized the flawed logic in that second statement, which is definitely wrong. The first part is still true though.

20190613, 18:31  #9 
Apr 2019
5×41 Posts 
Also just to answer my original question: I see now that what I was describing is just a form of sieve.
And after a little more research, looking at gmpfermat source for example, found that it basically sieves according the above incongruence. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Stockfish game: "Move 8 poll", not "move 3.14159 discussion"  MooMoo2  Other Chess Games  5  20161022 01:55 
Antipoverty drug testing vs "high" tax deduction testing  kladner  Soap Box  3  20161014 18:43 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 