Number Theory Number Theory Math Forum

October 14th, 2015, 05: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
Quote:
 Originally Posted by mobel There is no need to factorize n-1. All you need to know is n-1 odd or even If it is even then you split in 2. As long as it is even you continue splitting in 2.
What happens if it's no longer even and you haven't found any factors? Do you declare it prime? October 14th, 2015, 05: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
Quote:
 Originally Posted by mobel Computing gcds does not require factorization at all!
Correct. Even the 'naive' Euclidean algorithm does it pretty quickly, certainly much more quickly than factoring. Further, computing (say)
$$\gcd\left(2^{(p-1)/2}+1,n\right)$$
doesn't require working with huge numbers: you can use modular exponentiation to find $2^{(p-1)/2}\pmod n$ and then find the gcd. So for example, with n = 7500234831103067317545753367960619620902953277223, I find $2^{(n-1)/2}\equiv1\pmod n$ and so $\gcd(2^{(p-1)/2}+1,n)=\gcd(2,n)=1.$ If I had to find $2^{(n-1)/2}$ explicitly it wouldn't fit in the universe.

So this part isn't a problem. October 14th, 2015, 05:45 AM   #33
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by CRGreathouse What happens if it's no longer even and you haven't found any factors? Do you declare it prime?
I have the solution when its no longer even and become odd.
First when n-1 stay even k times (for example) do you recognize that many pseudo-prime numbers will be eliminated? yes or no?
Second when n-1 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 n-1 when other primality tests USE THE FACTORIZATION OF N-1.
So my conclusion is that you are sabotaging my idea. You are dishonest.
You did not correct Al-Mahed many times.
561 failed my test and you know it you did not correct.
Computing gcd does not require factorization of n-1 you did not correct Al-Mahed until I post my correction.

Im 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.

Im 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, 07:11 AM   #34
Senior Member

Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
 Originally Posted by CRGreathouse Correct. Even the 'naive' Euclidean algorithm does it pretty quickly, certainly much more quickly than factoring.
Correct if you are reading "factoring" as getting all primes and their powers. If I can get any divisor of a number, which is what is intended here, then this I call "a factor", the same for getting a gcd, so clearly to compute a gcd is to compute a factor and that's what was meant.

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, 07: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
Quote:
 Originally Posted by al-mahed Just a matter of terminology: in this sense, to claim that finding gcd's does not involve any factorization is absurd.
I disagree, but perhaps our disagreement is merely one of terminology. Let me put it this way. Given a million-digit number, I can find the gcd of that number with RSA-2048 in about 2 milliseconds, even though factoring RSA-2048 is not possible with current technology (not even with millions of dollars' worth of computer time).

Last edited by CRGreathouse; October 14th, 2015 at 07:53 AM. October 14th, 2015, 10: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{n-1}{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 million-digit number, say it is $n$. Now $2^\frac{n-1}{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 million-digit number, which I cannot conceive how many digits such power of 2 would have; call it "unspoken-digit number". Now the question: RSA2048 can find the gcd of two given million-digit numbers in 2 milliseconds as I understood it, but is it the case if the million-digit number is tested against the "unspoken-digit number"? October 14th, 2015, 10:43 AM   #37
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by al-mahed Correct if you are reading "factoring" as getting all primes and their powers. If I can get any divisor of a number, which is what is intended here, then this I call "a factor", the same for getting a gcd, so clearly to compute a gcd is to compute a factor and that's what was meant. 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}$.
That is not what you said sir.
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?

- you did not read carefully what was written
- your goal was just to sabotage my idea.
Im not rude! Im honest and I dislike people playing the teachers without having enough knowledge to do it.

Im not teacher (I was tens of years ago).
Im 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 Im 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.
Im old now and I do not have enough energy to focus on calculations.
Im not mad but I will never ever be kind even with my brothers when they act or say something wrong. October 14th, 2015, 11: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:
 Originally Posted by al-mahed RSA2048 can find the gcd of two given million-digit numbers in 2 milliseconds as I understood it
A small correction here: RSA-2048 is just a number, one with 617 decimal digits. I picked it only because it's known to be hard to factor.

Quote:
 Originally Posted by al-mahed But let me now just pose a question taking your example: We have such a million-digit number, say it is $n$. Now $2^\frac{n-1}{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 million-digit number, which I cannot conceive how many digits such power of 2 would have; call it "unspoken-digit number". Now the question: RSA2048 can find the gcd of two given million-digit numbers in 2 milliseconds as I understood it, but is it the case if the million-digit number is tested against the "unspoken-digit number"?
This is a good question -- it shows that you've been paying attention. Yes, this is quite a bit harder than finding the gcd of the million-digit number with another million-digit number (or even easier, the gcd of the million-digit number with RSA-2048).

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 million-digit numbers.

Here are some order of magnitude estimates on the time needed:
• Find gcd of a 617-digit number with a million-digit number: 2 ms
• Multiply two million-digit numbers: 20 ms
• Find gcd of two million-digit numbers: 0.5 seconds
• Compute a modular exponentiation with a million-digit modulus and exponent: 1 week October 15th, 2015, 02:13 AM   #39
Member

Joined: Oct 2013

Posts: 60
Thanks: 6

Quote:
 Originally Posted by CRGreathouse I disagree, but perhaps our disagreement is merely one of terminology. Let me put it this way. Given a million-digit number, I can find the gcd of that number with RSA-2048 in about 2 milliseconds, even though factoring RSA-2048 is not possible with current technology (not even with millions of dollars' worth of computer time).
Correct. The euclidian gcd algorithm is one of the best developed ever.

Here's an amazing example:
Someday a spy gives us a 'secret' number A=m*p:
Code:
23628542307141981241869560860159046098340361824025619659548500025775322220096370349965444223173235616148122970792396418281481383022650981891922027692667343340689504264580618823412688321464938202931103160890890100964641014541824824305460266838847531046185922338984604982241517890753508023878559165753236302547176182719498313289212514733359728962494853073355084849877786361675646187011443947062748479632148325865522285256844949541254811427385125732834560592234448784454051056397689
Trying to factorize the number will take months and years of intense computations.
Small chance to reveal the message m within a lifetime.

Then someday another spy gives us number B=m*q:
Code:
73388221100734851384386742176828049006448498778457457535953122929017416833624142727586441442982113060083729476893370704651207503752095428362302320772755519312854759908951743677154937975118174637116716231763272528182432263522485096825521224250965224397381191955358946383972337439987020677622852371840582614159070609330095850441960341997818010873921972711774600685806035463965298546632731399313076922710696707363120769649370657933907141217818113129631703776441583847943639113905937`
Again unable for a factorisation of B, we soon realize that gcd(A,B) will reveal m immediately(<10ms). Math is fun. 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 on-theme 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 think-tank where every member can contribute.

Last edited by Martin Hopf; October 15th, 2015 at 02:33 AM. Tags breaking, fermat, news, pseudoprimes ,

### fermat numbers news

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post fafa Number Theory 4 July 10th, 2013 12:25 PM usermind Number Theory 1 October 5th, 2010 10:30 AM Mathworm Abstract Algebra 1 March 5th, 2009 03:20 PM reddmann Number Theory 2 August 30th, 2007 09:03 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      