mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-08-02, 06:38   #12
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Default

Quote:
Originally Posted by Citrix View Post
To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small
That still leaves surprisingly large search space.

How big is N? Less than 1000 bits? More than million bits?

How small is m? Less than 1000? More than million?
axn is offline   Reply With Quote
Old 2020-08-02, 06:40   #13
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Default

Quote:
Originally Posted by retina View Post
Okay. But it still doesn't meet the criterion 99%.

log(6¹⁰⁰)/log(7×6¹⁰⁰+11) = 98.92...%

Indeed for any integer N I can't see how you ever get 99%. The only way would be something like e×e⁹⁹+0 = 99%. So k=e, b=e, n=99, c=0. And other multiples of those values.
Ah! You're thinking 99% as an exact number, whereas I'm pretty sure OP intended to give the general flavor of the structure of the number. Meaning, b^n part is the dominant term.
axn is offline   Reply With Quote
Old 2020-08-02, 07:25   #14
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

Quote:
Originally Posted by axn View Post
That still leaves surprisingly large search space.

How big is N? Less than 1000 bits? More than million bits?

How small is m? Less than 1000? More than million?
N~ 100,000 bits +
m <1000

We could also define k and c to be less than 2^64.
Citrix is online now   Reply With Quote
Old 2020-08-02, 16:47   #15
axn
 
axn's Avatar
 
Jun 2003

112668 Posts
Default

Quote:
Originally Posted by Citrix View Post
To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small
Quote:
Originally Posted by Citrix View Post
N~ 100,000 bits +
m <1000

We could also define k and c to be less than 2^64.
Let's take m=1000 so we have the largest search space.

When N is about 1e5 bits, the first n that satisfies m*n > b is n_min~=4500, and b_max ~=4.5 million

When N is about 1e6 bits, it is n_min ~= 39600 and b_max ~=39.6 million.

For the above numbers, it should be feasible to brute force all prime b's < b_max. Basic outline of the algorithm would be to do c = N % (b^k), (prime b from 2 to b_max) where b^k is about 256 bits (>> our target c with is < 64 bits).
If |c| < 2^64, we may have a potential solution, so trial factor N-c upto b_max and see if we get a complete factorization.
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
More Power!!!! petrw1 Teams 10 2019-10-15 17:36
TDP as power used? CRGreathouse Hardware 9 2016-02-06 18:46
Power 2 JohnFullspeed Miscellaneous Math 45 2011-07-10 20:13
testing, if a number is a power bitblit Math 8 2009-04-24 02:48
IBM Power 6 Unregistered Information & Answers 7 2008-08-30 14:36

All times are UTC. The time now is 01:36.

Thu Dec 3 01:36:23 UTC 2020 up 83 days, 22:47, 1 user, load averages: 2.35, 1.94, 1.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.