October 14th, 2015, 04:01 AM  #31 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  
October 14th, 2015, 04:15 AM  #32 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Correct. Even the 'naive' Euclidean algorithm does it pretty quickly, certainly much more quickly than factoring. Further, computing (say) $$ \gcd\left(2^{(p1)/2}+1,n\right) $$ doesn't require working with huge numbers: you can use modular exponentiation to find $2^{(p1)/2}\pmod n$ and then find the gcd. So for example, with n = 7500234831103067317545753367960619620902953277223, I find $2^{(n1)/2}\equiv1\pmod n$ and so $\gcd(2^{(p1)/2}+1,n)=\gcd(2,n)=1.$ If I had to find $2^{(n1)/2}$ explicitly it wouldn't fit in the universe. So this part isn't a problem. 
October 14th, 2015, 04:45 AM  #33  
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Quote:
First when n1 stay even k times (for example) do you recognize that many pseudoprime numbers will be eliminated? yes or no? Second when n1 at some stage become odd WE DO NOT NEED to factorize it. I have the solution but I will keep it for me. You know why? Because you did not say that it is ASTRONOMICAL to factorize n1 when other primality tests USE THE FACTORIZATION OF N1. So my conclusion is that you are sabotaging my idea. You are dishonest. You did not correct AlMahed many times. 561 failed my test and you know it you did not correct. Computing gcd does not require factorization of n1 you did not correct AlMahed until I post my correction. I`m not going to spend my time correcting each one who did not read my posts. It is a waste of time. No one talks about the core of my test. NO ONE. Only comments are either out of the subject either comments of bad faith like yours. I`m not playing the victim as you claimed nor Galileo stuff. Here you see clearly that you are de "MAUVAISE FOI". Your goal is not to help. No. You goal is to play the teacher. Did you post any of your works? NOOOOOOOOOOOOOOOOOO Did you suggest any idea to be discussed? NOOOOOOOOOOOOOO You are just answering as if you are a teacher. You are a BAD TEACHER because you have no knowledge of mathematics. You are a programmer (not even of high level I know programmers of high level) who claim to be mathematician. You use the computer before using a paper and pen. Now that I have said what I have to say good luck to your forum. Try to encourage others to participate. As long as you are dominating the forum the forum will have no future. If you for some reason you stop participating the forum will sink.  
October 14th, 2015, 06:11 AM  #34  
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47  Quote:
Just a matter of terminology: in this sense, to claim that finding gcd's does not involve any factorization is absurd. If that suits it better, instead of saying "you need to factorize decreasing $2^x$", say "you need to find the gcd of decreasing $2^x$", what anyway seems worse than computing $n$ against a list of previously given primes smaller than $\sqrt{n}$.  
October 14th, 2015, 06:42 AM  #35 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  I disagree, but perhaps our disagreement is merely one of terminology. Let me put it this way. Given a milliondigit number, I can find the gcd of that number with RSA2048 in about 2 milliseconds, even though factoring RSA2048 is not possible with current technology (not even with millions of dollars' worth of computer time).
Last edited by CRGreathouse; October 14th, 2015 at 06:53 AM. 
October 14th, 2015, 09:34 AM  #36 
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47 
Yes, I guess it is just a matter of terminology, maybe mine was misleading, but I meant to say that usually, in worst (and likely most) case scenarios, transferring the problem from $n$ to $2^\frac{n1}{2^y}$ powers that way increases wildly the complexity, but in general this is obviously not very precise because "given some method to calculate the gcd" is very vague. So the comment was addressing that particular method against working with $n$ by any other known means. But let me now just pose a question taking your example: We have such a milliondigit number, say it is $n$. Now $2^\frac{n1}{2^y}\pm 1$ for the first steps of the intended method, i.e., for small $y$, will give us approximately floor(n*log(2)/log(10)) + 1 for $n$ being the milliondigit number, which I cannot conceive how many digits such power of 2 would have; call it "unspokendigit number". Now the question: RSA2048 can find the gcd of two given milliondigit numbers in 2 milliseconds as I understood it, but is it the case if the milliondigit number is tested against the "unspokendigit number"? 
October 14th, 2015, 09:43 AM  #37  
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Quote:
You are just trying to escape by getting into terminology problem. You said that you need the factorization to compute the gcd and you add that it will be very complicated to do it. I quote you : "so now you are let to factorize not n but a series of astronomically larger power of 2" Why such dishonesty? To save you ego? Your comments are wrong for 2 reasons :  you did not read carefully what was written  your goal was just to sabotage my idea. I`m not rude! I`m honest and I dislike people playing the teachers without having enough knowledge to do it. I`m not teacher (I was tens of years ago). I`m not a programmer. I do not know all the mathematical technics in detail. But I can understand a proof. I can understand what tool could be used to solve some problem. I can solve lot of problems by taking new approaches and imaginative ways. After all of that I`m honest not tricky guy. I apologize when I say something wrong. I recognize my errors each time I make a mistake. When I was on "lycee" (college?) I was the first one in mathematics out of 3500 students. I had never be noted less than 20 out of 20. I`m old now and I do not have enough energy to focus on calculations. I`m not mad but I will never ever be kind even with my brothers when they act or say something wrong.  
October 14th, 2015, 10:03 AM  #38  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
Quote:
Almost all of your time is spent on modular exponentiation, not on the gcd itself. The exponentiation will take about 3.3 million squarings and a few million multiplications, all of which will be on milliondigit numbers. Here are some order of magnitude estimates on the time needed:
 
October 15th, 2015, 01:13 AM  #39  
Member Joined: Oct 2013 Posts: 60 Thanks: 6  Quote:
Here's an amazing example: Someday a spy gives us a 'secret' number A=m*p: Code: 23628542307141981241869560860159046098340361824025619659548500025775322220096370349965444223173235616148122970792396418281481383022650981891922027692667343340689504264580618823412688321464938202931103160890890100964641014541824824305460266838847531046185922338984604982241517890753508023878559165753236302547176182719498313289212514733359728962494853073355084849877786361675646187011443947062748479632148325865522285256844949541254811427385125732834560592234448784454051056397689 Small chance to reveal the message m within a lifetime. Then someday another spy gives us number B=m*q: Code: 73388221100734851384386742176828049006448498778457457535953122929017416833624142727586441442982113060083729476893370704651207503752095428362302320772755519312854759908951743677154937975118174637116716231763272528182432263522485096825521224250965224397381191955358946383972337439987020677622852371840582614159070609330095850441960341997818010873921972711774600685806035463965298546632731399313076922710696707363120769649370657933907141217818113129631703776441583847943639113905937 This was a rather uncommon example in cryptography but amusing I hope. m is the secret project i'm working on at the moment. But seriously, also pointing to mobel, I wish we can someday build a workshop here on interesting topics. A place where we discuss ontheme and peacefully, developing something really new. Every mathematician has his ideas. Constructive criticism is a necessity,but also politeness and respect for each other. I see this forum as a thinktank where every member can contribute. Last edited by Martin Hopf; October 15th, 2015 at 01:33 AM.  

Tags 
breaking, fermat, news, pseudoprimes 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fermat primes  fafa  Number Theory  4  July 10th, 2013 11:25 AM 
Problems driving me crazy.(Primes,Fermat,Euler)  usermind  Number Theory  1  October 5th, 2010 09:30 AM 
Pseudofinite fields  Mathworm  Abstract Algebra  1  March 5th, 2009 02:20 PM 
PseudoDiophantine Nuisance  reddmann  Number Theory  2  August 30th, 2007 08:03 AM 