Question

Project factoring need c++ code

Because there are some numbers are very large, like 1316872907073608066468826571215294289 i really want to know how to read the file with this kind of numbers and store

For this project you will be factoring numbers, significantly smaller than the numbers used for RSA of course, but they will still be fairly large numbers. So large in fact that if you are using C++ you may not be able to natively represent these numbers. If you choose to use C++ for this project you will need to determine a way to store the number so that they can be used in your program. I would recommend the GNU Multiple Precision Library (GMP). Examine their webpage for download and use instructions.

In addition to factoring there will be some RSA messages given to you that you may choose to decipher, if you can factor the public key.

You will be given a list of many numbers and asked to factor them as quickly as you can. We only briefly talked about factoring integers in class with the naive algorithm. You will certainly have to find speed ups. There are some obvious speed ups, you don’t have to check every power of two, or every power of 3 or 5 or 7 etc this allows you to skip significantly many numbers. Using this you will be able to factor some of the earlier numbers in a reasonable amount of time.

There are other methods to factoring. All of the numbers in the given list are of the form pq for primes p and q. Meaning that once you have one factor you have both. This means that really all you need are prime numbers, if you can generate a list of large enough primes then you can factor all of these numbers.

Other methods of factoring include Pollard’s Rho, Pollard’s p−1, Quadratic Sieve. You may choose to look into some of these advanced options to help speed up your program, though if you decide not to that is fine as well.

Your work should include:

your program which reads numbers from a file and attempts to factor them

the list of numbers you are factoring

the output of your program in the form of

n=p∗q

for each n in the input file

the part of nums.txt: space splits each number

the file is too large I can't upload all, if you need plz left the email address
2605796209 2665827481 2727241729 2771188489 2835030001 2847758989 2913364501 2947078369 2981297941 3028508869 3034591009 3049979869 3095847409 3102585613 3104500681 3112189369 3167168281 3170523661 3174061717 3227199289 3258128161 3292343689 3299509573 3316369789 3383314189 3390678073 3410910409 3471883141 3533945809 3541966741 3549675937 3605282209 3613129213 3678058609 3686064013 3694086841 41446029193 42400845937 42442670821 43420447789 44076646753 44107007209 45123126481 45136546141 45294525253 46383710641 46906519489 47313779749 47418505357 48202589989 48266148793 48403775341 48558765529 49240451593 49347624901 49426792021 49436926573 49577203729 50258987461 50316828829 50349646933 50424523621 50462936941 50534274097 50575834357 50719343161 51365002009 51416833549 51509581597 51707129329 52257783793 52401858409 52515912613 52574733733 52723914409 52839107029 53448971581 53461677337 53545385293 54027422233 54056392861 54131813401 54180724909 54925816081 55024893793 55099462549 55574633353 56192853709 56211702949 56334049393 56560910977 56721402421 57110211853 57501432889 57571982173 57605156617 57735342529 57745514209 58529316661 58634894533 58734132973 58861969561 58900790929 59028990253 59710792261 59788260757 59818501333 59840754577 59948698081 60453354121 60857023393 61534005829 62085486193 62220617101 62776134229 62912768353 659212462561 670273603393 675064369117 675933082189 685715093737 689155888693 691297462249 691504953301 701536176193 705032381437 712816484953 716765373301 718405829821 718835176069 730973795281 732512263453 732897246253 733277922109 738697256569 742777903561 746577218209 747813671929 752540927773 753147874753 759889718449 762259130221 766861701157 770637079081 773336724961 777369373801 780569962993 783321054721 786310262821 787160732989 788464970857 788541416233 789922699681 794608781293 796326585793 796372965613 798059814301 798848808301 799385406397 800827374541 800856650749 802559408293 803050397389 804798260473 805218456337 807503261701 811748994181 812914654837 814719481717 818608014409 818759911093 820053051049 820084657177 820541966401 831176906761 833412873001 834712150501 836308942069 836794093573 839168494729 840423040333 845043330853 846919489573 849342599821 849814051789 850708706461 851163996517 851258628481 851561690101 852243253933 852612699409 853415139457 859082435689 860632469401 865005152761 868392659353 868442176081 868909408789 870320658073 870332366317 882466188361 884386902277 884541330793 886310353921 894381098029 897632687953 900179718469 903251155141 909113888257 910799928421 911132295937 912558954121 914205069913 925365020893 927419509213 928208819641 937912834681 940574160013 943243036849 944044483693 946099224601 946140444013 948199746841 948851358373 953508898417 953509746349 955228881601 956214477541 957939341173 959406519769 969364300969 970554490201 971112884857 971734986529 972864622921 989105521021 990146149801 991429879021 992301232357 994243058833 1002458690113 1005303164149 1007915849797 1009071652621 1009733974741 1011267927097 1019128053241 1020966403273 1048000590961 1059658702933 1071446501449 2827441619389 2892579068101 2916948245941 2950884291541 2973274730869 2984147711869 3006901937269 3016274273413 3018865562269 3041771823421 3085761971917 3089985417769 3101728176541 3102089631661 3138179629261 3142302578209 3154584486409 3161991210349 3173184527269 3187803236161 3207719973373 3214693665481 3224890433761 3227258519281 3234883007761 3249359950849 3292709110189 3296352241873 3298597714261 3302598938293 3337287762409 3341747410489 3348634348021

Answer 1

main.py

# Importing necssary libraries
from unRSA import *
import sys
import time

# Want to record the total time elapsed
start_time = time.time()

# Grabbing the user input from the command line
inInput = map(long,sys.argv[1:])
inInput = inInput[0]
print inInput

# Reading in the test file
with open("testlist.txt", 'r') as f:
    data = f.readlines()

# Here the text file data is mapped correctly
data = map(int,data)

# Calling the find factor function to find the first factor
p = findOneFactor(inInput)

# Dividing the number by the factor found above to find the second factor
q = inInput/p

# Printing and calculated the elapsed time
print "We have p = ",p," and q = ",q
elapsed_time = time.time()-start_time
print "The elapsed time is: "
print elapsed_time

unRSA.py

from math import sqrt

def findOneFactor(n):

    # Only have to check up to the sqrt(n)
    m = int(sqrt(n))

    # Checking 2 first before entering the loop
    if n % 2 == 0:
        return 2

    # starting the loop at 3
    i = 3

    while (i<=(m)):
        # checking if the factor has been found
        if n % i == 0:
            return i
        # We increment the loop by two to skip even numbers
        i = i+2