$ factor 2374879348234927493

cppig1995의 이미지

$ factor 2374879348234927493

2374879348234927493 : 19 124993649907101447

정말 큰 소수를 하나 얻었습니다.
다른 분들의 경험은 어떤가요?

wkpark의 이미지

흠 coreutils에 이런 유틸이 있었군요 @.@

Quote:
$ factor 2374879348234927497
2374879348234927497: 3 79 10020587967235981

온갖 참된 삶은 만남이다 --Martin Buber

찬밥의 이미지

몇번의 시도 끝에..

$ factor 9384098250837927293
9384098250837927293: 9384098250837927293

htna의 이미지

근데 저거 정말 솟수 입니까 ?
음.. 맞는지 확인하려면 무지 오래 걸릴것 같은데요...
정말 맞는지 확인하려면요..
쓸데없는 딴지였습니다.
^^;

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

Prentice의 이미지

쓸데없이(?) 의심만 하지 마시고 직접 실행해보세요. -_-

찬밥님 숫자 확인의 경우 오래 걸립니다..

다콘의 이미지

htna wrote:
근데 저거 정말 솟수 입니까 ?
음.. 맞는지 확인하려면 무지 오래 걸릴것 같은데요...
정말 맞는지 확인하려면요..
쓸데없는 딴지였습니다.
^^;

요즘 mathematica를 배우고 있는지라 찾아봤습니다.
PrimeQ를 쓰면 위에 나온 수들은 1초 이내에 prime number인지 아닌지 알 수 있습니다.
몇번째 prime number인지 궁금해서 계산해보니 하루종일 계산하고 있어서 꺼버렸습니다. ;)

정태영의 이미지

Quote:
root # factor 9475879348234927491
9475879348234927491: 3 3158626449411642497

생각없이 숫자를 몇 개 변경 해보니 -_-!! 한 50초 동안 돌더니.. 이런 결과가 나오는군요 꺄르르르

오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

htna의 이미지

제가 물어보던것은 approximated prime number 인지 real prime number 인지 입니다..
어떤 주어진 number가 있을때 이것이 real prime number인지를 확인하는 방법이 constant or linear time에 찾는 방법이 나왔나요 ???
NP-problem 혹은 exponential-time에 찾을 수 있는게 아닌가 해서 입니다.
대부분의 알고리즘이 approximated prime number인지를 확인하는게 아닐까 해서 입니다.
만약 위의 값들이 real prime number이며 이의 알고리즘이 충분히 빠른 시간에 응답가능한 것이라면,
RSA와 같은 large prime number에 근거한 security algorithm 등에 치명적인 영향을 줄거라 생각되었기 때문입니다.

PS:
에궁 제가 학부를 졸업한지 쬐끔(??) 되어서 많이 잊어먹었네요.
혹시 틀린부분 혹은 보충할만한 부분이 있다면 여러 고수님들의 지적바랍니다.

다콘 wrote:
htna wrote:
근데 저거 정말 솟수 입니까 ?
음.. 맞는지 확인하려면 무지 오래 걸릴것 같은데요...
정말 맞는지 확인하려면요..
쓸데없는 딴지였습니다.
^^;

요즘 mathematica를 배우고 있는지라 찾아봤습니다.
PrimeQ를 쓰면 위에 나온 수들은 1초 이내에 prime number인지 아닌지 알 수 있습니다.
몇번째 prime number인지 궁금해서 계산해보니 하루종일 계산하고 있어서 꺼버렸습니다. ;)

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

랜덤여신의 이미지

barosl@deathnote:~$ time factor 9384098250837927293
9384098250837927293: 9384098250837927293

real    0m54.595s
user    0m44.191s
sys     0m0.191s

제컴에선 요렇군요;

차리서의 이미지

wkpark wrote:
흠 coreutils에 이런 유틸이 있었군요 @.@
Quote:
$ factor 2374879348234927497
2374879348234927497: 3 79 10020587967235981

제대로 찾아보지도 않은 채, 당연히 없으리라고 생각하여 지금껏 직접 만들어서 써왔습니다. 게다가 더욱 ‘털썩’스럽게도, 실행 파일의 이름이 제가 만들어서 쓰던 놈과 같군요. OTL

--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!

ed.netdiver의 이미지

http://bbs.kldp.org/viewtopic.php?t=50541&start=0&postdays=0&postorder=asc&highlight=factor

몇달전엔가 유사한 쓰레드가 있었던것 같아 찾아보니 나오네용^^;

역쉬, 자게만 죽돌해도 쏠쏠한 정보들이...ㅎㅎ

--------------------------------------------------------------------------------
\(´∇`)ノ \(´∇`)ノ \(´∇`)ノ \(´∇`)ノ
def ed():neTdiVeR in range(thEeArTh)

Prentice의 이미지

htna wrote:
제가 물어보던것은 approximated prime number 인지 real prime number 인지 입니다..
어떤 주어진 number가 있을때 이것이 real prime number인지를 확인하는 방법이 constant or linear time에 찾는 방법이 나왔나요 ???
NP-problem 혹은 exponential-time에 찾을 수 있는게 아닌가 해서 입니다.
대부분의 알고리즘이 approximated prime number인지를 확인하는게 아닐까 해서 입니다.
만약 위의 값들이 real prime number이며 이의 알고리즘이 충분히 빠른 시간에 응답가능한 것이라면,
RSA와 같은 large prime number에 근거한 security algorithm 등에 치명적인 영향을 줄거라 생각되었기 때문입니다.

실제로 coreutils 소스를 받아보셨다면 wheel factorization을 사용함을 쉽게 아실 수 있으셨을 것입니다.

http://primes.utm.edu/glossary/page.php?sort=WheelFactorization

---

소인수 분해 프로그램의 결과가 소수가 아니라면 정말 치명적인 버그일 것입니다.

coyday의 이미지

후아.. prime number 찾기 되게 힘드네요..
한 스무번 정도 했더니 10자리짜리 하나 건졌네요.

현재 남아 있는 지적 호기심을 자극하는 수학 난제 중 상당 부분이 소수 관련한
내용인 것 같던데.. 신비한 수의 세계~

1111111111111111111 이것두네요..

북한산(X) 삼각산(O) 백운대(X) 백운봉(O)

htna의 이미지

다음은 검은해님께서 링크하신
http://primes.utm.edu/glossary/page.php?sort=WheelFactorization
의 뒷부분을 해석한 것입니다.
머. 해석에 오류가 있으면 지적해 주시기 바랍니다.
보시면 알겠지만, 여기서 제시하는 wheel 을 이용한 prime판별법이란, approximated prime number를 빠른시간에 판별하는 법 입니다. real prime number를 판별하는 방법이 아닙니다.
먼저 말씀드렸다시피 large number의 prime판별법이 이미 constant or linear or logarithmic(거의 linear와 같이 취급됩니다) - time에 해결되는 알고리즘이 나왔다면, RSA와같이 large prime number를 이용한 암호화 알고리즘은 이미 무용지물이 되었어야 합니다.
그럼.

Quote:
This has misled many to suppose that such wheels (and patterns) are good "generators" of primes.
이것을 많은사람들이 그러한 wheels(and patterns)이 훌륭한 primes 의 generator라고 잘못 이끌어 왔다.

They are not.
그것들은 그렇지 않다.

The density of primes decreases as the integers increase in size (see the prime number theorem),
(prime number theorem을 보라), integer의 크기가 증가함에 따라 prime의 밀도가 줄어든다.

so when we apply these same wheels to a list of large integers, almost all of those that are not removed by the wheel are composite.
그래서 그러한 같은 wheels을 large integer들의 list에 적용할때, wheel에 의해 제거되지 않는 대부분은 composite 이다.
(wheel방법에 의하면, wheel에 의해 제거되는 것들이 composite이고, 제거되지 않는 부분이 prime이라고 하고 있습니다. wheel이 충분히 크면요. ^^;; )

Notice that the simple wheel based on 2 and 3 removed 4/6 = 2/3 rds of the composites.
2와 3에 의한 간단한 wheel이 composites의 4/6 = 2/3 rds를 제거한다. (rds가 뭐죠??? 머의 약자였지.. ?? ㅡ.ㅜ)

The larger wheel using 2, 3, 5, and 7 will remove 162/210 (over 77%) of the composites.
2, 3, 5와 7을 이용한 larger wheel은 composites의 162/210(77%를 넘는) 를 제거할 것이다.

Large wheels are not particularly efficient.
large wheels은 특히 효율적이지 않다.

To remove 90% of the composites, we must use the primes up to 257.
90%의 composites를 제거하기 위해, 우리는 257개 까지의 pimes를 사용해야만 한다.

95% requires the primes to 75,037.
95% 는 75,037 개의 primes를 요구한다.

96% requires the primes to 1,246,379.
96% 는 1,246,379 개의 primes를 요구한다.

97% requires the primes to 134,253,593!
97% 는 134,253,593(와우!) 의 primes를 요구한다.

Just imagine how many primes you will need to remove 99% of the composites!
단지 상상해봐라, 99%의 composites를 제거하기 위해 얼마나 많은 primes가 필요하게 될지를...

검은해 wrote:
htna wrote:
제가 물어보던것은 approximated prime number 인지 real prime number 인지 입니다..
어떤 주어진 number가 있을때 이것이 real prime number인지를 확인하는 방법이 constant or linear time에 찾는 방법이 나왔나요 ???
NP-problem 혹은 exponential-time에 찾을 수 있는게 아닌가 해서 입니다.
대부분의 알고리즘이 approximated prime number인지를 확인하는게 아닐까 해서 입니다.
만약 위의 값들이 real prime number이며 이의 알고리즘이 충분히 빠른 시간에 응답가능한 것이라면,
RSA와 같은 large prime number에 근거한 security algorithm 등에 치명적인 영향을 줄거라 생각되었기 때문입니다.

실제로 coreutils 소스를 받아보셨다면 wheel factorization을 사용함을 쉽게 아실 수 있으셨을 것입니다.

http://primes.utm.edu/glossary/page.php?sort=WheelFactorization

---

소인수 분해 프로그램의 결과가 소수가 아니라면 정말 치명적인 버그일 것입니다.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

Prentice의 이미지

저는 소수에 대해 잘 모릅니다. ^^; 흠.. wheel factorization이라면 실제로 나눗셈에 의한 검증을 exhaustive하게 수행하여 real prime을 찾는 과정이나 이와 유사한 과정일 줄로 짐작하고 있었습니다. 꼭 그렇지 않다는 말씀이신가요..?

아무튼, 소스를 직접 열어보셨더라면 쉽게 확인하실 수 있으셨을 것입니다.

---

말씀대로라면 소인수분해 프로그램에 버그가 있을 수도 있다는 것인가요..?

chronon의 이미지

-rds 는

2/3 이 two thi-rd + s 라서 쓴 것 아닐까요

htna의 이미지

wheel factorization이 실제로 나눗셈에 의한 방법을 합니다만, exhaustive하게 검사하지는 않습니다.
몇몇 대략적인 체를 가지고 대략적으로/확률적(?)으로 걸러내는 것이지요.
소스를 열어본 것은 아니지만, 그 소인수분해 프로그램이 wheel factorization을 이용한다면, 프로그램에 버그가 있는것이 아니라 알고리즘 자체가 exhaustive한 검사방법이 아니란 것입니다.
즉 프로그램이 사용한 알고리즘 자체가 exhaustive하지 않기 때문에, 프로그램 자체가 exhaustive하게 real prime number를 걸러내지 못한다는 것입니다.
버그와는 다른 문제 입니다.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

실러캔스의 이미지

coyday wrote:
후아.. prime number 찾기 되게 힘드네요..
한 스무번 정도 했더니 10자리짜리 하나 건졌네요.

현재 남아 있는 지적 호기심을 자극하는 수학 난제 중 상당 부분이 소수 관련한
내용인 것 같던데.. 신비한 수의 세계~

1111111111111111111 이것두네요..

1111....1111 의 형태로 구성된 수 중에 소수가 존재하는지의 여부를 판단하는 것도 이미 연구된 적이 있는 주제입니다.

A(n)을 1이 n개 있는 수라고 정의했을 때

현재 A(2), A(19), A(23), A(317), A(1031) 가 소수로 알려져 있다는 내용을 읽은 기억이 납니다.

매우 오래된 (20년 가까이 지난) 저널에서 본 내용이라 지금은 더 많은 수가 발견되었을 수 있겠죠 :D

p.s.
위에서 논의되고 있는 내용 중 "단순히 소수인지 아닌지의 여부를 판별하는 것" 과 "소인수 분해" 는 차원이 다른 문제입니다. 소수 여부를 판별하는 문제 자체는 이미 APRCL판정법 같이 상당히 빠른 방법이 개발되어 있습니다. (APRCL이후의 판정법은 저의 지식이 미천한 관계로 잘 모르겠습니다)

즐잠~ 나도 자야지

htna의 이미지

chronon wrote:
-rds 는
2/3 이 two thi-rd + s 라서 쓴 것 아닐까요

오호라~ 그럴수가 있군요...

인용좀 하겠습니다.

Quote:
$ factor 2374879348234927497
2374879348234927497: 3 79 10020587967235981

에서 알 수 있는것은 10020587967235981는 prime number라고 알 수 있습니다.
하지만, 10020587967235981이 정말로 prime number 일까요?
http://bbs.kldp.org/viewtopic.php?t=50541&start=0&postdays=0&postorder=asc&highlight=factor
에 링크로 있는
http://www.math.com/students/calculators/source/prime-number.htm
에 넣어보니...

Please enter a number: 10020587967235981
Is Prime ? 10020587967235980 is not prime. It is divisible by 2.
라고 나옵니다.
이것만 봐서도 factor에서 결과로 나오는 prime number는 approximated prime number라는것을 반증할 수있지 않을까요 ?

real prime number 구하는거...
그리 쉽지 않습니다.
그것만 linear/logarithmic(에궁 이글자 왜이리 어려워.. ㅡ.ㅜ)-time에 구하는 알고리즘만 발견(?!) 해도...
대박일겁니다.
전세계 은행(and xxx)들 초!! 비상 걸릴걸요...

PS:
아닐라나.. 아님 말구요...
무책임하게 느껴지셨다면 죄송합니다.
저두 내용을 붙이면서, 약간 과장한 느낌이 드네요..
(정말 과장일지. 사실일지는 모르겠습니다만...)
그나저나.. APRCL 어디서 구할 수 있죠. 궁금해지네요...

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

wkpark의 이미지

htna wrote:
chronon wrote:
-rds 는
2/3 이 two thi-rd + s 라서 쓴 것 아닐까요

오호라~ 그럴수가 있군요...

인용좀 하겠습니다.

Quote:
$ factor 2374879348234927497
2374879348234927497: 3 79 10020587967235981

에서 알 수 있는것은 10020587967235981는 prime number라고 알 수 있습니다.
하지만, 10020587967235981이 정말로 prime number 일까요?
http://bbs.kldp.org/viewtopic.php?t=50541&start=0&postdays=0&postorder=asc&highlight=factor
에 링크로 있는
http://www.math.com/students/calculators/source/prime-number.htm
에 넣어보니...

Please enter a number: 10020587967235981
Is Prime ? 10020587967235980 is not prime. It is divisible by 2.
라고 나옵니다.
이것만 봐서도 factor에서 결과로 나오는 prime number는 approximated prime number라는것을 반증할 수있지 않을까요 ?

real prime number 구하는거...
그리 쉽지 않습니다.
그것만 linear/logarithmic(에궁 이글자 왜이리 어려워.. ㅡ.ㅜ)-time에 구하는 알고리즘만 발견(?!) 해도...
대박일겁니다.
전세계 은행(and xxx)들 초!! 비상 걸릴걸요...

PS:
아닐라나.. 아님 말구요...
무책임하게 느껴지셨다면 죄송합니다.
저두 내용을 붙이면서, 약간 과장한 느낌이 드네요..
(정말 과장일지. 사실일지는 모르겠습니다만...)
그나저나.. APRCL 어디서 구할 수 있죠. 궁금해지네요...

Quote:
Please enter a number: 10020587967235981
Is Prime ? 10020587967235980 is not prime. It is divisible by 2.

? 위의 메시지는 그냥 단지, 원래 값에서 1을 빼니 2로 나누어지더라는 말이 아닌가요? 입력한 숫자 10020587967235981이 prime number 가 아니라는 뜻은 아닌데요. ^^;;

3이나 5를 넣으니 소수라는 메시지가 나오고,
1233331230를 넣으니,
1233331230 is not prime. It is divisible by 2.라고 나오지만요.

http://www.alpertron.com.ar/ECM.HTM 에서 테스트 하니 소수라고 판별되네요.

온갖 참된 삶은 만남이다 --Martin Buber

bigdog의 이미지

15자리 넘어가면
Ouch!
이렇게 나옵니다.

참고로, sparcII solaris9(64bit) 입니다.

puzzlet의 이미지

어떤 자연수가 소수인지 판별하는 다항시간 알고리즘이 있습니다. 반면 소인수분해는 아직 NP인 모양입니다.

From http://mathworld.wolfram.com/PrimalityTest.html

Quote:
Unlike prime factorization, primality testing was long believed to be a P-problem (Wagon 1991). This had not been demonstrated, however, until Agrawal et al. (2002) unexpectedly discovered a polynomial time algorithm for primality testing that has asymptotic complexity of O(ln^12(n)) (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002).

발발다빠따반반나다발딸발발다빠따따맣발발다뿌
멓터벅더떠벋떠벌더벌벌떠벌떠더법벍떠더벌벌떠

htna의 이미지

wkpark wrote:
3이나 5를 넣으니 소수라는 메시지가 나오고,
1233331230를 넣으니,
1233331230 is not prime. It is divisible by 2.라고 나오지만요.

오호~
http://www.math.com/students/calculators/source/prime-number.htm
사이트 버그이군요..
죄송합니다. 초보티 팍팍 냈습니다. ㅡ.ㅜ
(머얌.. 저 싸이트.. 내가 값을 확인하지 않은것도 있지만. ㅡ.ㅜ, 지멋대로 값을 바꿔서 판별을 하는군요.. 어떤알고리즘이지. ?? ㅋㅋ)

puzzlet wrote:
어떤 자연수가 소수인지 판별하는 다항시간 알고리즘이 있습니다. 반면 소인수분해는 아직 NP인 모양입니다.
From http://mathworld.wolfram.com/PrimalityTest.html
Quote:
Unlike prime factorization...

여기서 mathworld사용하는분 만나니 반갑네요.. ^^
polynomial time에 가능하군요. 새로운것 배웠습니다.
역시나 제가 좀 오바~ 를 한듯 합니다.
지송합니다.
^^;;;

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

chronon의 이미지

htna wrote:
사이트 버그이군요..

확인해 봤는데

정확히 말해서 사이트 버그라기보다 자바스크립트 버그가 아닌가 합니다..
10020587967235981 라는 숫자 자체가 제대로 저장이 되지 않는군요.

<script language="javascript">
var num = 10020587967235981;
alert (num);
</script>

결과 :

10020587967235980

WinXP IE6 에서 테스트했습니다.
불여우에서는 어떤가요?

bear의 이미지

[xxxx@xxxx xxxx]$ time factor 9384098250837927293
9384098250837927936
Ouch!

real    0m0.044s
user    0m0.020s
sys     0m0.010s
[xxxxx@xxxx xxxx]$

이런 엄청난 결과가....

FruitsCandy의 이미지

[root@Embedded TEMP]# factor 9999999999999999919
9999999999999999919: 9999999999999999919

fator에서 뽑아낸 가장 큰 소수입니다 :)

아지랑이류 초환상 공콤 화랑... 포기하다.. T.T

lifthrasiir의 이미지

먼저 wheel factorization은 정확합니다. 즉 이 과정으로 나온 결과는 실제 그 숫자의 소인수분해 결과와 일치합니다. (rho가 생각나서 잘못 쓸 뻔 했군요. -.-) 원래 sieve를 사용하는 알고리즘은 소수의 리스트를 저장하고 있는데, wheel factorization은 소수 리스트를 버리고 "대충 봐서 합성수인 것들만 버리고" 나머지 숫자를 가지고 trial division을 해 보는 방식입니다. (예를 들어서 6으로 나눈 나머지가 1이나 5인 것으로만 테스트한다던지...) 당연히 error가 날래야 날 수가 없죠.

prime glossary의 마지막 문장은 단순히 이런 방식을 쓰는 게 소수 리스트를 쓰는 것보다 시간면에서는 효율적이지 않다는 걸 뜻합니다. (wheel을 무진장 크게 만드는 건 쓸데없이 합성수로 나눠 보는 경우를 최대한 줄이기 위해서인데, 이 가능성을 줄이려면 wheel을 무진장 크게 만들어야 한다는 소리입니다.) 대신, 메모리는 무진장 절약되겠지요.

그리고... repunit prime(1111...111 따위의 소수)는 아직도 (10^1031 - 1)/9 = 111...111(1031자리)가 최고 기록입니다. prime pages에 따르면 더 큰 probable prime은 몇 개 더 있다고 하더군요.

- 토끼군

B00m의 이미지

FruitsCandy wrote:
[root@Embedded TEMP]# factor 9999999999999999919
9999999999999999919: 9999999999999999919

fator에서 뽑아낸 가장 큰 소수입니다 :)

9999999999999999961: 9999999999999999961

angpoo의 이미지

제 전화번호를(01x-***-****) 넣어보니
1x*******: ## ### ### ###
앞에 1을 빼면
x*******: x*******
솟수입니다. (소수라는 표기는 영 어색해서 솟수라고 씁니다)
제 전화번호를 국번까지 그대로 010으로 바꿀 수 있다면 전체가 솟수가 됩니다.
그리고 전화번호 4자리만 보면 솟수이고 뒤에서 3자리나 5자리만 봐도 솟수입니다.
#에 사용된 숫자는 전부 제 전화번호에 있는 숫자들입니다.
위에서 x가 뭔지까지 말하면 제 전화번호가 밝혀집니다.

경고! 위에것만으로 제 전화번호를 알아 낼 수 있다고 해서 절대 게시판에 올리거나 전화를 걸지는 말아주세요. 저는 모르는 남자나 직업적인 말투의 여성에게서 오는 전화를 아주 싫어합니다.

htna의 이미지

권순선님 사실인가요?
^^

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra