mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2019-05-24, 01:39   #1
hansl
 
hansl's Avatar
 
Apr 2019

5·41 Posts
Default 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
hansl is offline   Reply With Quote
Old 2019-05-24, 03:12   #2
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

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?
hansl is offline   Reply With Quote
Old 2019-05-24, 07:39   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

134810 Posts
Default

That sounds like a version of Mastermind!
Nick is offline   Reply With Quote
Old 2019-05-24, 07:48   #4
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

9,859 Posts
Default

Quote:
Originally Posted by hansl View Post
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
xilman is offline   Reply With Quote
Old 2019-05-24, 09:14   #5
hansl
 
hansl's Avatar
 
Apr 2019

5·41 Posts
Default

Quote:
Originally Posted by xilman View Post
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?
hansl is offline   Reply With Quote
Old 2019-05-24, 21:22   #6
hansl
 
hansl's Avatar
 
Apr 2019

5·41 Posts
Default

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<<sh+j+k,p)==r,result[j+1]++;result[k+1]++);
            );
        );
        nonzero=0;
        for(x=1,p,if(result[x]==0,print("Mod(",x-1","p")"),nonzero++));
        prd *= p/nonzero;
        \\print("\n", p-nonzero, "/", 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,p-1,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);
I have a suspicion that there's probably some much simpler way to calculate this that does not require O(p2) steps for each prime. Maybe these results are obvious to someone more mathematically inclined, but I'm confused about what these values fundamentally represent?

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 2019-05-24 at 21:38
hansl is offline   Reply With Quote
Old 2019-05-24, 22:44   #7
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

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,p-1,
            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)));
}
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.

Man, what a way to overcomplicate things...

Last fiddled with by hansl on 2019-05-24 at 22:53
hansl is offline   Reply With Quote
Old 2019-05-26, 00:35   #8
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

Quote:
Originally Posted by hansl View Post
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.
hansl is offline   Reply With Quote
Old 2019-06-13, 18:31   #9
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

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.
hansl is offline   Reply With Quote
Reply

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 2016-10-22 01:55
Anti-poverty drug testing vs "high" tax deduction testing kladner Soap Box 3 2016-10-14 18:43
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

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

Thu Apr 9 10:31:07 UTC 2020 up 15 days, 8:04, 1 user, load averages: 1.29, 1.36, 1.31

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.