mersenneforum.org > Math Is there an "anti"-CRT?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-05-24, 01:39 #1 hansl     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 (ai mod pi) for many primes pi, is it possible to then determine what x is? Last fiddled with by hansl on 2019-05-24 at 01:40
 2019-05-24, 03:12 #2 hansl     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/(p-1), 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/(p-1.);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 ... So if I have one incongruence per prime up to 195199289, then there are still 1/34 of all integers remaining which x could be?
 2019-05-24, 07:39 #3 Nick     Dec 2012 The Netherlands 25048 Posts That sounds like a version of Mastermind!
2019-05-24, 07:48   #4
xilman
Bamboozled!

May 2003
Down not across

100110100000112 Posts

Quote:
 Originally Posted by hansl Hrm, after calculating a little bit, it seems that this is pretty awful concept if I can only tell one incongruence per prime. ... So if I have one incongruence per prime up to 195199289, then there are still 1/34 of all integers remaining which x could be?
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 2019-05-24 at 07:48 Reason: Fix tpo

2019-05-24, 09:14   #5
hansl

Apr 2019

5×41 Posts

Quote:
 Originally Posted by xilman 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.
In a way, I guess you're right, but I've also discovered something else that is way more astounding (to me anyways).

I have been experimenting with algorithms to see if I can tell anything about fermat factors. It is known that for Fn, any factors will be of the form k*2n+2+1

So, given some unfactored composite C of Fn,
C can be factored into
C = (k1*2n+2+1)(k2*2n+2+1)
which can be expanded and rearranged to:
(C-1)/2n+2 = k1*k2*2n+2+(k1+k2)

So, the interesting thing I discovered is that using this equivalence, given any Fn, and prime p>2, I have an algorithm that produces exactly one incongruence (mod p) which seems to apply to all ki on that Fn.
It gives the same result for any variation of input: Fn, or combination of its factors(or even a single known factor by itself), or unfactored composites C.

Any ideas why this would be so?

 2019-05-24, 21:22 #6 hansl     Apr 2019 110011012 Posts Well, anyways, here's the PARI code, it just tries all combinations of j,k (aka k1 k2) (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=(n-1)>>sh, p, prd=1.); print("x="x); forprime(p=2,100000, r=Mod(x,p); result=vector(p,dummy,0); for(j=0,p-1, for(k=j,p-1, if(Mod(j*k<
 2019-05-24, 22:44 #7 hansl     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<
2019-05-26, 00:35   #8
hansl

Apr 2019

110011012 Posts

Quote:
 Originally Posted by hansl So basically if Fn != 0 (mod p) then k != -1/2n+2(mod p) But since this modular inverse will never result in 0, the incongruence holds regardless if you even check Fn (mod p)==0.
Just realized the flawed logic in that second statement, which is definitely wrong. The first part is still true though.

 2019-06-13, 18:31 #9 hansl     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 gmp-fermat source for example, found that it basically sieves according the above incongruence.

 Similar Threads Thread Thread Starter Forum Replies Last Post MooMoo2 Other Chess Games 5 2016-10-22 01:55 kladner Soap Box 3 2016-10-14 18:43 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 10:59.

Thu Apr 9 10:59:41 UTC 2020 up 15 days, 8:32, 1 user, load averages: 1.16, 1.23, 1.28