RSA Factorization problem

Posted by dada on Stack Overflow See other posts from Stack Overflow or by dada
Published on 2010-04-15T15:59:20Z Indexed on 2010/04/15 16:03 UTC
Read the original article Hit count: 315

Filed under:

rsa

|

factorisation

|

algorithm

|

problem-solving

At class we found this programming problem, and currently, we have no idea how to solve it.

The positive integer n is given. It is known that n = p * q, where p and q are primes, p<=q and |q-k*p|<10^5 for some given positive integer k. You must find p and q.

Input:

35 1
121 1
1000730021 9

Output:

5 * 7
11 * 11
10007 * 100003

It's not a homework, we are just trying to solve some interesting problems. If you have some ideas, please post them here so we can try something, thanks.

© Stack Overflow or respective owner

Related posts about rsa

Ubuntu 9.10 RSA authentication: ssh fails, filezilla runs fine

as seen on Server Fault - Search for 'Server Fault'
This is quite a mistery for me. I usually use passwordless RSA authentication to login into my remote *nix servers with ssh and sftp. Never had any problem until now. I cannot connect to an Ubuntu 9.10 machine: user@myclient$ ssh -i .ssh/Ganymede_key [email protected] [...] debug1: Host… >>> More
Can you help me get my head around openssl public key encryption with rsa.h in c++?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi there, I am trying to get my head around public key encryption using the openssl implementation of rsa in C++. Can you help? So far these are my thoughts (please do correct if necessary) Alice is connected to Bob over a network Alice and Bob want secure communications Alice generates a public… >>> More
Unable to install Perl Crypt::OpenSSL::RSA module, please help

as seen on Server Fault - Search for 'Server Fault'
Hi Everyone, I spent several hours but unable to install CPAN Crypt::OpenSSL::RSA module. It's required for Postfix's dkimproxy add-on. What I do is to run the following command in the shell: $ perl -MCPAN -e 'install Crypt::OpenSSL::RSA' When I run this command, several lines displayed and at… >>> More
OCR an RSA key fob (security token)

as seen on Stack Overflow - Search for 'Stack Overflow'
I put together a quick WinForm/embedded IE browser control which logs into our company's bank website each morning and scrapes/exports the desired deposit information (the bank is a smallish regional bank). Since we have a few dozen "pseudoaccounts" that draw from the same master account, this actually… >>> More
BN_hex2bn magicaly segfaults in openSSL

as seen on Stack Overflow - Search for 'Stack Overflow'
Greetings, this is my first post on stackoverflow, and i'm sorry if its a bit long. I'm trying to build a handshake protocol for my own project and am having issues with the server converting the clients RSA's public key to a Bignum. It works in my clent code, but the server segfaults when attempting… >>> More

Related posts about factorisation

Factorising program not working. Help required.

as seen on Stack Overflow - Search for 'Stack Overflow'
I am working on a factorisation problem using Fermat's Factorization and for small numbers it is working well. I've been able to calculate the factors (getting the answers from Wolfram Alpha) for small numbers, like the one on the Wikipedia page (5959). Just when I thought I had the problem licked… >>> More
RSA Factorization problem

as seen on Stack Overflow - Search for 'Stack Overflow'
At class we found this programming problem, and currently, we have no idea how to solve it. The positive integer n is given. It is known that n = p * q, where p and q are primes, p<=q and |q-k*p|<10^5 for some given positive integer k. You must find p and q. Input: 35 1 121 1 1000730021… >>> More
Preallocate memory for a program in Linux before it gets started

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, folks, I have a program that repeatedly solves large systems of linear equations using cholesky decomposition. Characterising is that I sometimes need to store the complete factorisation which can exceed about 20 GB of memory. The factorisation happens inside a library that I call. Furthermore… >>> More
Require help with program for edutainment game

as seen on Stack Overflow - Search for 'Stack Overflow'
I am working on a factorisation problem and for small numbers it is working well. I've been able to calculate the factors (getting the answers from Wolfram Alpha) for small numbers, like the one on the Wikipedia page (5959). Along with the Wikipedia page I have been following this guide. Once again… >>> More
Problem with Boost::Asio for C++

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi there, For my bachelors thesis, I am implementing a distributed version of an algorithm for factoring large integers (finding the prime factorisation). This has applications in e.g. security of the RSA cryptosystem. My vision is, that clients (linux or windows) will download an application and… >>> More