Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Help with a factorisation, Please [Important]
Replies: 5   Last Post: Jan 17, 2014 11:05 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
David Bernier

Posts: 3,330
Registered: 12/13/04
Re: Help with a factorisation, Please [Important]
Posted: Jan 17, 2014 10:55 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 01/17/2014 09:31 AM, Hlauk wrote:
> On Friday, January 17, 2014 4:24:35 AM UTC-5, David Bernier wrote:
>> On 01/17/2014 01:02 AM, Hlauk wrote:
>>

>>> On Thursday, January 16, 2014 8:13:16 PM UTC-5, Port563 wrote:
>>
>>>> "Hlauk" <hlauk.h.bogart@gmail.com> wrote...
>>
>>>>
>>
>>>> On Tuesday, January 14, 2014 1:37:57 AM UTC-5, Hlauk wrote:
>>
>>>>
>>
>>>>> --------------------------------------------------------------------
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> Your largest composite with 1699 digits ---
>>
>>>>
>>
>>>>> 250780990473277239463501902261407456853671185585833450252893481769741630104113953160117929526585384293341515238703323548911661032764408015576591313360839395919966387613242233729062478419014754086862937444452424191447596937331224271127229558183501526823983863038468719035807492495067809781569318418174268789774205219229050615996697771558382207300172539908748741702950342509920018117853875587915450274732963247978386751867782501651120604171542082467327650075770189332694760714057465146634671093770804135210091959056942677724629940434363320673496931601665092850303566268598000624438512292742356623483214721771008090540756498021065973482998396687767048046332417464726799131784206041171727126716111737522791039154871410777689151314805474424749188085936901532239183090561382998573484106909898359446635302869979182280412951503356027637689082495154437999919144203689286297811955421958975173958170822792867997404948541064781976763258130044045751514109288270926372851836266171555650450575694405471834059
82
>>
>> 45325602511255244250207904704121983163309894950931458712809580594862337802500418398431405480893860157182072480132320585828889914529391213150639488900110069086872461727290576704598789739555487214162249774467649923114928283271931634840282117207293377910135595752147127557251622558326421157857414637362020364123648587909877696219093586729789995137470194719156642385692199285919411113718990106768290110675682960300014511068937681320680843298237148951823441428351943405242753083069015608592612389742057748503592682293924554770508834146124744108391100201797587401627078021473436036153227723256430759847253758147206996347241255869426284445333291765102703844080551306884674006671923619625045833456199941934043201
>>

>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> OK, I verified this is the same as (from my post):
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> 2507809904732772394635019022614074568536711855858334502528934
>>
>>>>
>>
>>>> 817697416301041139531601179295265853842933415152387033235489116610
>>
>>>>
>>
>>>> 327644080155765913133608393959199663876132422337290624784190147540
>>
>>>>
>>
>>>> 868629374444524241914475969373312242711272295581835015268239838630
>>
>>>>
>>
>>>> 384687190358074924950678097815693184181742687897742052192290506159
>>
>>>>
>>
>>>> 966977715583822073001725399087487417029503425099200181178538755879
>>
>>>>
>>
>>>> 154502747329632479783867518677825016511206041715420824673276500757
>>
>>>>
>>
>>>> 701893326947607140574651466346710937708041352100919590569426777246
>>
>>>>
>>
>>>> 299404343633206734969316016650928503035662685980006244385122927423
>>
>>>>
>>
>>>> 566234832147217710080905407564980210659734829983966877670480463324
>>
>>>>
>>
>>>> 174647267991317842060411717271267161117375227910391548714107776891
>>
>>>>
>>
>>>> 513148054744247491880859369015322391830905613829985734841069098983
>>
>>>>
>>
>>>> 594466353028699791822804129515033560276376890824951544379999191442
>>
>>>>
>>
>>>> 036892862978119554219589751739581708227928679974049485410647819767
>>
>>>>
>>
>>>> 632581300440457515141092882709263728518362661715556504505756944054
>>
>>>>
>>
>>>> 718340598245325602511255244250207904704121983163309894950931458712
>>
>>>>
>>
>>>> 809580594862337802500418398431405480893860157182072480132320585828
>>
>>>>
>>
>>>> 889914529391213150639488900110069086872461727290576704598789739555
>>
>>>>
>>
>>>> 487214162249774467649923114928283271931634840282117207293377910135
>>
>>>>
>>
>>>> 595752147127557251622558326421157857414637362020364123648587909877
>>
>>>>
>>
>>>> 696219093586729789995137470194719156642385692199285919411113718990
>>
>>>>
>>
>>>> 106768290110675682960300014511068937681320680843298237148951823441
>>
>>>>
>>
>>>> 428351943405242753083069015608592612389742057748503592682293924554
>>
>>>>
>>
>>>> 770508834146124744108391100201797587401627078021473436036153227723
>>
>>>>
>>
>>>> 256430759847253758147206996347241255869426284445333291765102703844
>>
>>>>
>>
>>>> 080551306884674006671923619625045833456199941934043201
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>> It's two equal length prime divisors (almost divisors ;-) that pass the
>>
>>>>
>>
>>>>> Rabin\ECM prime check routine.
>>
>>>>
>>
>>>>> Each have 850 digits.
>>
>>>>
>>
>>>>> 1416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807585172453732300928844166217497513339011609552754760919432516613342515934207128898323163882601844369732916068174529024861277545319487121471318760920620239340889401489931662342201511922351961295458131967951747811556037841876042724783551666212991970250914479154838122415284133433810002231952457010874393873648375474828092884155484954150665010040649757624512486556720828457365151063247005373731824240405315952807
>>
>>>>
>>
>>>>> *
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>> 1770526018141491614407259702105100764853320993433918854323143311828504559932281568403417164774129727767937973233258960531417869154791449718757166263352175084205902906411830149870782190611494853119159500850627921132314967534864622853968281878451296339249552996839810639903047368948159314728787456210040455400379720320243257005672775658799271345813421955207157078958926088995352495877342479165872567062949759368661982825535716205490253234626149634159872442901796752029687494869421240126801755023653346857933983845087465422809197335301053824637618390891818836163045387587785956197009705433494726504331049316206029065561153849895620105141406304181518409968975495678735572997371533634997521094733104882238457865188663927542646216364735063353512995572269827640397882974905439707087911820392750572584187225969534614037631650962011453192523104153734860286207
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> OK, their product is:
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> 2507809904732772394635019022614074568536711855858334502528934
>>
>>>>
>>
>>>> 817697416301041139531601179295265853842933415152387033235489116610
>>
>>>>
>>
>>>> 327644080155765913133608393959199663876132422337290624784190147540
>>
>>>>
>>
>>>> 868629374444524241914475969373312242711272295581835015268239838630
>>
>>>>
>>
>>>> 384687190358074924950678097815693184181742687897742052192290506159
>>
>>>>
>>
>>>> 966977715583822073001725399087487417029503425099200181178538755879
>>
>>>>
>>
>>>> 154502747329632479783867518677825016511206041715420824673276500757
>>
>>>>
>>
>>>> 701893326947607140574651466346710937708041352100919590569426777246
>>
>>>>
>>
>>>> 299404343633206734969316016650928503035662685980006244385122927423
>>
>>>>
>>
>>>> 566234832147217710080905407564980210659734829983966877670480463324
>>
>>>>
>>
>>>> 174647267991317842060411717271267161117375227910391548714107776891
>>
>>>>
>>
>>>> 513148054744247491880859369015322391830905613829985734841069098983
>>
>>>>
>>
>>>> 594466353028699791822804129515033560276376890824951544379999191442
>>
>>>>
>>
>>>> 036892862978119554219589751739581708227928679974049485410647819767
>>
>>>>
>>
>>>> 632581300440457515141092882709263728518362661715556504505756944054
>>
>>>>
>>
>>>> 718340598245325602511255244250207904704121983163309894950931458712
>>
>>>>
>>
>>>> 809580594862337802500418398431405480893860157182072480132320585828
>>
>>>>
>>
>>>> 889914529391213150639488900110069086872461727290576704598789739555
>>
>>>>
>>
>>>> 487214162249774467649923114928283271931634840282117207293377910135
>>
>>>>
>>
>>>> 595752147127557250844728429820046612378504904853272516739292947225
>>
>>>>
>>
>>>> 066807891058876965460238429071539770341127021354286561627703549774
>>
>>>>
>>
>>>> 034055911674583516166539973954550875737988869787406172532125894957
>>
>>>>
>>
>>>> 799322449958952254336458637651616571353096259583644577791390792684
>>
>>>>
>>
>>>> 136681347381041272054978946086366240554307431354448479560112832384
>>
>>>>
>>
>>>> 391699305252179237024194426842152350253762960181356406133002579643
>>
>>>>
>>
>>>> 628445350566157023487860488049102964562235014925033049
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> and the difference between it and "my" number is:
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> 777829896601111245036132457167091606909294962652629411202527
>>
>>>>
>>
>>>> 852824534899041123179386301258670844999357783410169216072712378436
>>
>>>>
>>
>>>> 092166793760040556518061943331811055892064616825928483629029493446
>>
>>>>
>>
>>>> 290498746610377956976041036645798164859014890903131870633827486765
>>
>>>>
>>
>>>> 083472053412154115431346847319646667024956476040395338864731454595
>>
>>>>
>>
>>>> 074521123012569505088905615663324263976885632100124200452105956318
>>
>>>>
>>
>>>> 516983184063131575942868893964927009010152
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> which is impressively small. :-)
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>> = a semi prime composite with the first 1267 high order digits the same
>>
>>>>
>>
>>>>> as your composite.
>>
>>>>
>>
>>>>> 250780990473277239463501902261407456853671185585833450252893481769741630104113953160117929526585384293341515238703323548911661032764408015576591313360839395919966387613242233729062478419014754086862937444452424191447596937331224271127229558183501526823983863038468719035807492495067809781569318418174268789774205219229050615996697771558382207300172539908748741702950342509920018117853875587915450274732963247978386751867782501651120604171542082467327650075770189332694760714057465146634671093770804135210091959056942677724629940434363320673496931601665092850303566268598000624438512292742356623483214721771008090540756498021065973482998396687767048046332417464726799131784206041171727126716111737522791039154871410777689151314805474424749188085936901532239183090561382998573484106909898359446635302869979182280412951503356027637689082495154437999919144203689286297811955421958975173958170822792867997404948541064781976763258130044045751514109288270926372851836266171555650450575694405471834059
82
>>
>> 45325602511255244250207904704121983163309894950931458712809580594862337802500418398431405480893860157182072480132320585828889914529391213150639488900110069086872461727290576704598789739555487214162249774467649923114928283271931634840282117207293377910135595752147127557250844728429820046612378504904853272516739292947225066807891058876965460238429071539770341127021354286561627703549774034055911674583516166539973954550875737988869787406172532125894957799322449958952254336458637651616571353096259583644577791390792684136681347381041272054978946086366240554307431354448479560112832384391699305252179237024194426842152350253762960181356406133002579643628445350566157023487860488049102964562235014925033049
>>

>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> This was derived from your composite!
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> Hint--- Look at the ratio between the two primes and tie that in with ---
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> (sqrt(of your composite))/(sqrt(ratio)) = start of smallest divisor.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Well, the ratio is very, very close to 1.25.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> So you computed SQRT(my composite)/SQRT(1.25) and then hunted for the first
>>
>>>>
>>
>>>> prime you encountered (via sieve? which program?) that was (say) larger than
>>
>>>>
>>
>>>> that.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Then divided it into my composite, found the quotient and found the first
>>
>>>>
>>
>>>> prime that was (say) smaller than it.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> I'd know which way around it was if I knew whether the ratio was more or
>>
>>>>
>>
>>>> less than 1.25.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>> This would make an interesting encryption scheme but oh-oh,
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Not too wise a one, if people know private keys will be close to
>>
>>>>
>>
>>>> 1.118033988749894848204586834365 and 1.118033988749894848204586834365^(-1)
>>
>>>>
>>
>>>> times the square root of the public key! :-)
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Yes, "randomly" deciding that ratio would be the key, and various posts by
>>
>>>>
>>
>>>> me
>>
>>>>
>>
>>>> in the discussion with pubkeybreaker brought that up.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> The ratio would need to be generated intelligently, as it otherwise would
>>
>>>>
>>
>>>> prove a vulnerability. For example, using a pseudorandom number generator
>>
>>>>
>>
>>>> that
>>
>>>>
>>
>>>> generated a 128 bit binary number from 0 to 2^128 - 1 and which was then
>>
>>>>
>>
>>>> used to get our ratio would significantly weaken a 512 bit encryption
>>
>>>>
>>
>>>> system.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> But I'm certain you meant that.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>> now the cat's out of the bag.
>>
>>>>
>>
>>>>> You would have your composite as the public key where the logical step
>>
>>>>
>>
>>>>> would be to find it's prime factors to access the private key but
>>
>>>>
>>
>>>>> this would not be so.
>>
>>>>
>>
>>>>> Instead your composite would be the public key and unbeknownst to
>>
>>>>
>>
>>>>> the one decrypting my semi-prime composite would be the mid level private
>>
>>>>
>>
>>>>> key which then would have to be factored for the final private key.
>>
>>>>
>>
>>>>> So a 5 or 6 fold whammy of deception is possible.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Yes, I was sure that was the path you were going to suggest. Interesting.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> I think it adds only one layer of complexity; "my" composite needs to have
>>
>>>>
>>
>>>> its smallest factor very large, else it will become obvious that it is not
>>
>>>>
>>
>>>> an "almost" prime (semi-prime).
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>> #1 Your composite need not be factored but if it was, it would be a dead
>>
>>>>
>>
>>>>> end.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Not quite. If it was even part-factored and that could be seen not to be
>>
>>>>
>>
>>>> the
>>
>>>>
>>
>>>> private key (or too small, so obviously not the private key), then they know
>>
>>>>
>>
>>>> what to do next and the one extra layer is guessing the ratio.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Not sure how the actual mechanism of public key cryptography would work,
>>
>>>>
>>
>>>> though.
>>
>>>>
>>
>>>> How would that which is encrypted via the public key be able to be
>>
>>>>
>>
>>>> decrypted,
>>
>>>>
>>
>>>> exactly?
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> pubkeybreaker may well be along soon; he knows much more about this area
>>
>>>>
>>
>>>> than I.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>> #2 On the other hand if the one decrypting is using your composite as a
>>
>>>>
>>
>>>>> catalyst
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> to iterate the smallest divisor to a predetermined stopping point which
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> in-itself ---
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> #3 creates possibilities almost uncountable because that is how many
>>
>>>>
>>
>>>>> discrete
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> semi - primes are possible with a composite of this size .
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> #4 Finding, in this case, a compatible smaller prime divisor match with
>>
>>>>
>>
>>>>> your
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> composite in smallest next_prime look-up with largest next_prime look-up
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> dividing into your composite. It is what I did to achieve my two factors
>>
>>>>
>>
>>>>> above.
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> #5 Many easy or complex ratio's can be used to construct these 2 degree
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> monic polynomials.
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> if a complex ratio is used and the composites is very large like yours the
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> look-up process can take days. I was lucky because I used a simple ratio
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> that created a 4 cycle (gap) polynomial that only took a day or two to
>>
>>>>
>>
>>>>> find the
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> two factors. I worked with some that had 1000 cycle but very hard
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> to find two matching factors. The 4 cycle gap that I used here is for
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> the small divisor only. The large divisor has a 5 cycle gap. This comes
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> automatically with the iterative process.
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> Some ratios will not work, these are rare, because of 0(mod 3) or
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> 0(mod 5) or even integers alternating between small and large divisors.
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> In the polynomial cycle where a small and large prime match is not
>>
>>>>
>>
>>>>> possible
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> because one or the other will be a 0(mod 3or5) or an even integer
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> thus no prime pair match is ever possible because of this alternating
>>
>>>>
>>
>>>>> pattern
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> between the two divisors.
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> These residuals can be checked when first starting the iterative process
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> for any particular ratio and not much work has to be done to either rule
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> in or rule out a certain ratio.
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> Cheers
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>>
>>
>>>>
>>
>>>>> Dan
>>
>>>>
>>
>>>> Again, using Port563 1699 digit composite to produce another prime pair from
>>
>>>>
>>
>>>> the
>>
>>>>
>>
>>>> same polynomial but skipping down stream from the last semi-prime created
>>
>>>>
>>
>>>> with a
>>
>>>>
>>
>>>> gap that equals 805 digits and then conducting the probable prime search.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> gap =
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> 2948602489324412628623949272393032074218793597790851845907327495026951131224194303203769964432571608251437251915411344242143959789812682523963954733972734669439197534906904112638208297009020407674421784458363420492449624523729161237704579371478537032780524187352664035667746086081038223365135829513283821227257315862017581919027211620909597263746901425097912401124193536464431552919968175146853859356886326538473880803166476350009972032457606829512595370401394508556838129116040181602448065712022505781729402748223521490142792454740633168221695922335657821374674969447393473222910395298402961973825046535416294674701529835525980988112169739641630367348266642330490652511339380504473424419543361083468300369433804477287189477423100758558261597650956345122052311503113850013209424497000018755752361789408078
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Just imagine how long it would take to find all the semi-primes within that
>>
>>>>
>>
>>>> gap!
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> The two new Rabin\ECM certified primes =
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> 1416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807585172453732300928844166217546704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696608543983
>>
>>>>
>>
>>>> *
>>
>>>>
>>
>>>> 1770526018141491614407259702105100764853320993433918854323143311828504559932281568403417164774129727767937973233258960531417869154791449718757166263352175084205902906411830149870782190611494853119159500850627921132314967534864622853968281878451296339249552996839810639903047368948159314728787456210040455400379720320243257005672775658799271345813421955207157078958926088995352495877342479165872567062949759368661982825535716205490253234626149634159872442901796752029687433380547502319371349237401318751850330995002612166966050645077153065049892267988518498722060992259717657549424426942322750901753580534034221821744452869899280028380364484570729047366710271490540313201675486608881880528773373990591002759103884547167454359577337817308552993957165148491966499540049897949888121541471781384807413917082717824804669044895535104954843942227120744547237
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> = semi-prime composite =
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> 2507809904732772394635019022614074568536711855858334502528934817697416301041139531601179295265853842933415152387033235489116610327644080155765913133608393959199663876132422337290624784190147540868629374444524241914475969373312242711272295581835015268239838630384687190358074924950678097815693184181742687897742052192290506159966977715583822073001725399087487417029503425099200181178538755879154502747329632479783867518677825016511206041715420824673276500757701893326947607140574651466346710937708041352100919590569426777246299404343633206734969316016650928503035662685980006244385122927423566234832147217710080905407564980210659734829983966877670480463324174647267991317842060411717271267161117375227910391548714107776891513148054744247491880859369015322391830905613829985734841069098983594466353028699791822804129515033560276376890824951544379999191442036892862978119554219589751739581708227925731371560160998019195818360188268366238721543302030863356401023335710584332310202553174090285768989
99
>>
>> 3888350595843900008063944914309300639345940216958724043370383059955433689862210101422385073219438372723709059639870961305160753291686633779160951867329544899519797691622830618517751516190351384648965953240392607252910701352904423219372519943546476485037683351022934020786413175509851871465524645547966945978265412144058590457881086844507853408916476169368946618464516157445587521947325968343889168801786763791750433060732945534129154237950836203559299977947774989504860863235727256318168391122434537109161496716091154301155366392929102315337315719017973911976940701937140179608358959972155944168710936654760622364865160776339859422798144535351623298506393039063043173474651063552102945806482653135624971e+1698
>>

>>>>
>>
>>>>
>>
>>>>
>>
>>>> Dividing each prime into the 1699 digit composite, the trailing zeros in the
>>
>>>>
>>
>>>> quotients = only 44
>>
>>>>
>>
>>>> This semi-prime is still well in range of the same triangle # index as the
>>
>>>>
>>
>>>> 1699
>>
>>>>
>>
>>>> digit composite.
>>
>>>>
>>
>>>> The previous primes when divided into 1699 digit composite had 417 trailing
>>
>>>>
>>
>>>> zeros.
>>
>>>>
>>
>>>> Where the best number of trailing zeros for any ratio could possibly be 424
>>
>>>>
>>
>>>> but
>>
>>>>
>>
>>>> highly unlikely.
>>
>>>>
>>
>>>> For each new high order digit that is attained in the search for these
>>
>>>>
>>
>>>> prime pairs the semi-primes that are found grow exponentially.
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Dan
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> ---------------
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>>
>>
>>>> Thank you for the entertaining idea!
>>
>>>
>>
>>> The trick in iterating the smallest divisor of your composite or any large
>>
>>> prime or composite is, first step ---(sqrt(your c))/(sqrt( r )).
>>
>>> (r) represents the selected ratio and in this case r = 1.25
>>
>>>
>>
>>> That produces the smallest of your smallest(int)divisor of your composite.
>>
>>> The next step is starting to build the polynomial with the smallest divisor.
>>
>>>
>>
>>> smallest divisor =
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428572988368918293191363646250175843311183122894983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>>
>>
>>> If int(small divisor) is even add 1 which I did here.
>>
>>>
>>
>>> Largest divisor below without remainder just to keep these numbers small
>>
>>> in this explanation.
>>
>>> The remainder of the largest divisor is important because this determines
>>
>>> what action to take on the smallest divisor for each following iteration.
>>
>>> There are many iterations especially with a composite and divisor of this size.
>>
>>>
>>
>>> 1.770526018141491614407259702105100764853320993433918854323143311828504559932281568403417164774129727767937973233258960531417869154791449718757166263352175084205902906411830149870782190611494853119159500850627921132314967534864622853968281878451296339249552996839810639903047368948159314728787456210040455400379720320243257005672775658799271345813421955207157078958926088995352495877342479165872567062949759368661982825535716235461147866489204557812719804138978903618729683380547502319371349237401318751850330995002612166966050645077153065049892267988518498722060992259717657549424426942322750901753580534034221821744452869899280028380364484570729047366710271490540313201675486608881880528773373990591002759103884547167454359577337817308552993957165148491966499540049897949888121541471781384807413917082717824804669044895535104954843942227120752613607e+849
>>
>>>
>>
>>>
>>
>>> There is no known algorithm for what is done next and many more steps
>>
>>> following to build this polynomial.
>>
>>>
>>
>>> Step#1
>>
>>> Add 10^424 as a trial to the smallest divisor.
>>
>>> All the next iteration will be - 10^423*n,- 10^422*n,-10^421*n, -10^420*n
>>
>>> where n could =[0,1,2,3,4,5,6,7,8,9] or skipping a -10^# because all 9's
>>
>>> are showing instead of zeros in the remainder. At times you have to add back the
>>
>>> last 10^# because of the nine's showing up in the remainder.
>>
>>> Keep dividing into the composite and take note of the remainder.
>>
>>> The key from here on is, building zeros starting with 1 zero and going
>>
>>> from there all the way to 424 trailing zeros in the quotient remainder.
>>
>>> Skipping the first few iterations just divide into the composite at the
>>
>>> pause point - e+416 or -10^416*n these examples below represent just my pause
>>
>>> points. You can divide each one and observe how the quotient remainder keeps
>>
>>> adding more and more zeros as you minus 10^#.
>>
>>> e+416 or - 10^416 limit for pause point below.
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345634193191363646250175843311183122894983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>>
>>
>>> next = e+412
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998691363646250175843311183122894983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>>
>>
>>> e+408 or - 10^408 is the limit for smallest divisor below.
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807646250175843311183122894983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>> e+407 or - 10^407 was the limit for the smallest divisor below.
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807646250175843311183122894983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>> e+405 - etc..
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807585250175843311183122894983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>> e+400
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807585172455843311183122894983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>> e+386
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807585172453732300928844194983746704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>> e+380
>>
>>> 1.416420814513193291525807761684080611882656794747135083458514649462803647945825254722733731819303782214350378586607168425134295323833159775005733010681740067364722325129464119896625752489195882495327600680502336905851974027891698283174625502761037071399642397471848511922437895158527451783029964968032364320303776256194605604538220527039417076650737564165725663167140871196281996701873983332698053650359807494929586260428573012345633998681807585172453732300928844166217546704438001855497079389921055001480264796002089733572840516061722452039913814390814798977648793807774126039539541553858200721402864427227377457395562295919424022704291587656583237893368217192432250561340389287105504423018699192472802207283107637733963487661870253846842395165732118793573199632039918359910497233177425107845931133666174259843735235916428083963875153781696602090887e+849
>>
>>>
>>
>>> etc...Note the progression of zeros in the remainder in each pause point above.
>>
>>>
>>
>>> As you will note I am just showing my pause points and not showing all the
>>
>>> iterations in between. I have become very used to doing this and will tackle
>>
>>> any large composite.
>>
>>
>>
>> How about the 130-digit composite number:
>>
>>
>>
>> 47485133560063190433548259679204355907477810307482663990525310023918\
>>
>> 21388435849831808696657092215642611599144927466443608010614619 ?
>>
>>
>>
>> dave

>
> Ok, I will get back to later on the above. I just got up and have to run an
> errand.
> What simple ratio would you like me to use between primes?
> (1.25),(1.125),(1.0625),(1.1),(1.2),(1.05) or a more complex one?
> Or I will just pick my own if you so wish.


I propose a ratio of about 1.01 .

dave


--
http://www.bibliotecapleyades.net/sociopolitica/last_circle/1.htm



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.