« previous next »
Pages: 1 ... 10 11 [12] 13 14   Go Down

Author Topic: New RSA Algorithm discussion  (Read 66761 times)

0 Members and 4 Guests are viewing this topic.

Offline Tribal

  • The Fallen
  • LV5 Advanced (Next: 300)
  • *
  • Posts: 218
  • Rating: +15/-1
    • View Profile
Re: New RSA Algorithm discussion
« Reply #165 on: July 15, 2011, 02:29:36 am »
***NECRODOUBLEPOST***

It's been awhile since I did anything with this because of so many factors, but I decided to write my tibasic code into C so I could use bigger primes.  I made a flowchart to help me figure out what exactly is going on since I haven't touched this in awhile, and for anybody who didn't really know it was that it was doing in the first place.  I'm still pursuing this because I have a strong feeling I was onto something, and it would be a great discovery.

Also, maybe this topic should be moved under the 'Math and Science' subforums?
« Last Edit: July 16, 2011, 04:26:49 am by Tribal »
Logged

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: New RSA Algorithm discussion
« Reply #166 on: July 15, 2011, 05:52:47 am »
Done. It'd be cool if something useful actually came out of this. We could use a great discovery, and it'd make all Nspire users happy. :D
Logged
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline ruler501

  • Meep
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2475
  • Rating: +66/-9
  • Crazy Programmer
    • View Profile
Re: New RSA Algorithm discussion
« Reply #167 on: July 15, 2011, 08:50:04 am »
Quote from: Tribal on July 15, 2011, 02:29:36 am
***NECRODOUBLEPOST***

It's been awhile since I did anything with this because of so many factors, but I decided to write my tibasic code into C so I could use bigger primes.  I made a flowchart to help me figure out what exactly is going on since I haven't touched this in awhile, and for anybody who didn't really know it was that it was doing in the first place.  I'm still pursuing this because I have a strong feeling I was onto something, and it would be a great discovery.

Also, maybe this topic should be moved under the 'Math and Science' subforums?
could you explain what the program is doing? The flow chart confused me...
I'd like to help if I could. Good luck at finding something
Logged
I currently don't do much, but I am a developer for a game you should totally try out called AssaultCube Reloaded download here https://assaultcuber.codeplex.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCM/CS/M/S d- s++: a---- C++ UL++ P+ L++ E---- W++ N o? K- w-- o? !M V?
PS+ PE+ Y+ PGP++ t 5? X R tv-- b+++ DI+ D+ G++ e- h! !r y

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #168 on: July 15, 2011, 11:09:41 am »
You really should mark yes and no on your flow chart.  Also, I don't know what ISQRT(p,q) is to know what X is.  I also don't know what you assume for P and Q.  Also, there are some nodes that have 3 outputs, too.
Logged

Offline Tribal

  • The Fallen
  • LV5 Advanced (Next: 300)
  • *
  • Posts: 218
  • Rating: +15/-1
    • View Profile
Re: New RSA Algorithm discussion
« Reply #169 on: July 15, 2011, 04:02:53 pm »
Quote from: graphmastur on July 15, 2011, 11:09:41 am
You really should mark yes and no on your flow chart.  Also, I don't know what ISQRT(p,q) is to know what X is.  I also don't know what you assume for P and Q.  Also, there are some nodes that have 3 outputs, too.
Sorry, I put 'False' on the false routes, so if it isn't false assume true.  I also fixed some mistakes and added a notes thing at the top.  Also, ISQRT is just integer sqrt, which can be thought of as the floored result of sqrt.  It's also less confusing with all the mistakes gone <_>

Updated flowchart: hhttp://i.imgur.com/ojm1J.png
« Last Edit: July 16, 2011, 04:26:29 am by Tribal »
Logged

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: New RSA Algorithm discussion
« Reply #170 on: July 15, 2011, 04:11:39 pm »
But how can ISQRT have two inputs?
Logged

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #171 on: July 15, 2011, 04:12:59 pm »
Quote from: t0xic_kitt3n on July 15, 2011, 04:11:39 pm
But how can ISQRT have two inputs?
That's what I'm trying to figure out.  I think it's finding the square root of N, actually.
Logged

Offline Tribal

  • The Fallen
  • LV5 Advanced (Next: 300)
  • *
  • Posts: 218
  • Rating: +15/-1
    • View Profile
Re: New RSA Algorithm discussion
« Reply #172 on: July 15, 2011, 04:27:03 pm »
Spoiler For IGNORE:
SQRT(X,Y) = SQRT(X/Y)
I don't really know why I was showing it like that, I'll fix it when I attempt to make it more speed efficient instead of space efficient.
Woops :-X

EDIT: AGH!  I'm just not thinking straight x.x
Yeah, it should be finding the sqrt of n like graphmastur said. Updated all flowchart links with the corrected version.

EDIT2: More flowchart errors addressed and all links (re)updated again.
EDIT3: I factored out some of the complexity of the former flowchart, here is the new one: http://i.imgur.com/sSkWK.png
EDIT4: One last error: The starting value of F should be 0 not 1 for the new flowchart.  I'm to lazy to upload another flowchart atm, so just so y'all know.
EDIT5: I got the C++ version done, source code is below.
Code: [Select]
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>

#define FPART(x) (float)(((float)x)-floor((float)x))

inline unsigned int isqrt(unsigned int n) {
    unsigned int i;
    for (i = 0; n >= (2*i)+1; n -= (2*i++)+1);
    return i;
}

int main(int argc, char *argv[]) {
    FILE *fp;
    unsigned int f, p, q, n, x, l;
    std::vector<unsigned int> xy;
    
    f = 1;
    p = atoi(argv[1]);
    q = atoi(argv[2]);
    n = p * q;
    x = isqrt(n);
    l = (p > q) ? q : p;

    for(; FPART(n/x) > FPART(n/(x+1)); --x);

    for(; x > l-1; ++f, --x) {
        if (FPART(n/x) > FPART(n/(x+1)))
            continue;
        xy.push_back(x);
        xy.push_back(f);
        f = 0;
    }
    
    fp = fopen("dataset", "w");
    fprintf(fp, "%u %u %zu ", p, q, xy.size());
    for (x = 0; x < xy.size(); ++x)
        fprintf(fp, "%u ", xy[x]);

    fprintf(fp, "\n");
    fclose(fp);

    return EXIT_SUCCESS;
}
« Last Edit: July 17, 2011, 12:17:15 am by Tribal »
Logged

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #173 on: July 16, 2011, 10:47:54 pm »
Okay, and have you tested how well it works?
Logged

Offline Tribal

  • The Fallen
  • LV5 Advanced (Next: 300)
  • *
  • Posts: 218
  • Rating: +15/-1
    • View Profile
Re: New RSA Algorithm discussion
« Reply #174 on: July 17, 2011, 04:38:50 am »
I'm not quite sure what you expect by 'working' but... As far as I know it outputs exactly what the TI-BASIC version would, except in a slightly different way.  It outputs everything to dataset, the first three numbers indicate the two primes entered, the third represents how much data there is.  After that it is just x, y coordinates one after another.  And of course it can handle larger numbers and is faster at what it does.  I'm still not exactly sure how to make a function from this data, I'll work more on that later.  The main reasons for making the C++ version was for the speed and to check and see if the pattern that I saw on the calculator's graph extended beyond numbers I couldn't test.
« Last Edit: July 17, 2011, 09:00:29 pm by Tribal »
Logged

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #175 on: July 17, 2011, 10:27:48 pm »
By working, I mean, not only does it do what you expected, but that it can in fact help factor them faster, and won't skip the factor accidentally.
Logged

Offline Tribal

  • The Fallen
  • LV5 Advanced (Next: 300)
  • *
  • Posts: 218
  • Rating: +15/-1
    • View Profile
Re: New RSA Algorithm discussion
« Reply #176 on: July 18, 2011, 01:36:26 am »
The program isn't really meant to *factor* anything.  It gets test data from doing a the comparison 'fpart(n/x) < fpart (n/(x+1))' where n is a semiprime and x is the current number counting down from sqrt(n).  If the condition is true, the number between the last successful comparison and the current comparison is stored as the y coordinate and the current 'x' is stored as the x coordinate.  For any semiprime numbers, this gives a graph that is always similar to http://i.imgur.com/lZKUX.png.

EDIT: That's kind of an old screenshot, but iirc that graph checks all numbers to zero instead of stopping at the factor.  I did this on purpose to see what the results were.  The C++ version would only show the last of the three asymptotes.
« Last Edit: July 18, 2011, 02:46:09 am by Tribal »
Logged

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: New RSA Algorithm discussion
« Reply #177 on: July 18, 2011, 03:10:32 am »
Can we close this topic until someone comes up with a practical crack of the RSA algorithm itself? I don't mean to be a downer, but here's the situation:

Given the current 2048 bit keys and classical computations, the scale of the problem is vastly more difficult than even the largest keys broken today (768 bits). By vast, I mean volume of the known universe measured in nanometers vast*. The chance that anyone will solve it is so exceedingly slim that the only mathematical tool I have available to calculate it has to work with arbitrary precision operations simply in order to present it. Unless someone gets their hands on a massive quantum computer running Shor's algorithm**, it is, in short, an impossible problem. Feel free to prove me wrong, but the community's CPU cycles could be better spent on other projects.

*Even this is an understatement.

**It'd take about 30 seconds for a quantum computer to break the code, since the computations necessary increase according to (lg n)^3 for an n bit key.
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #178 on: July 18, 2011, 01:31:31 pm »
That's why this topic exists. Don't close this topic at all.
Logged

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: New RSA Algorithm discussion
« Reply #179 on: July 18, 2011, 02:49:41 pm »
I have not read anything from previous posts, but I would just like to say that I still want to prove useful to this topic someday. I have been absorbing myself in mathematics-- particularly in number theory and prime numbers-- and I have filled up several notebooks since my vacation started. I have not found a way to factor in polynomial time, yet, but I believe that there is a way to factor specifically double prime numbers in polynomial time. I have made a way to deterministically (did I spell that correctly) test if a number is prime or composite and I am working on developing several new syntaxes for doing math that will help with these kinds of problems. One of these works on making new number systems with a slight modification to the definition of a prime number. For example, I have number sets where every single number is prime in that set, even though not all of them are prime in the set of natural numbers. If I can get anywhere with those number systems, I hope to apply the results to the natural numbers.

So for ideas, what if you defined a number to be prime so long as it is relatively prime to every number in the set? For example, {5,6,10,11} would have the primes as 5,6, and 11. If you work with a series such as {2,3,7,43,1+43*42...} every number is then "prime" to that set. Anywho, I hope I wasn't totally and completely off topic. I only had a few minutes to post before I get booted off the interwebs so I didn't read beyond the topic title.
Logged
Pages: 1 ... 10 11 [12] 13 14   Go Up
« previous next »