특수 제작 된 CPU를 사용하여 많은 수의 주요 요인을 찾습니다

https://stackoverflow.com/questions/1206277

05-07-2019
|

문제

저의 이해는 요즘 많은 공개 키 암호화 알고리즘이 키를 구성하기 위해 큰 소수에 의존하고 있으며, 암호화를 어렵게 만드는 두 가지 프라임의 제품을 고려하는 데 어려움이 있다는 것입니다. 또한 많은 수의 숫자를 고려하는 이유 중 하나는 너무 어렵다는 사실 중 하나는 사용 된 숫자의 크기가 CPU가 숫자에서 효율적으로 작동 할 수 없다는 것을 의미합니다. 1024, 2048 또는 4096 비트 숫자의 경우. 해당 숫자를 처리하려면 전문화 된 대형 정수 수학 라이브러리를 사용해야하며, CPU는 한 번에 작은 청크 (및 32 또는 64 비트) 만 보유 할 수 있으므로 라이브러리가 본질적으로 느려집니다.

그래서...

2048 비트 레지스터와 거대한 산술 회로를 갖춘 고도로 전문화 된 맞춤형 칩을 구축 할 수없는 이유는 8 ~ 16 ~ 32 ~ 64 비트 CPU와 같은 방식으로 훨씬 더 크게 구축해야합니까? 이 칩은 기존 CPU에서 대부분의 회로가 필요하지 않습니다. 결국 가상 메모리, 멀티 스레딩 또는 I/O와 같은 것을 처리 할 필요가 없습니다. 저장된 지침을 지원하는 일반 목적 프로세서 일 필요조차 없습니다. 거대한 숫자에 필요한 산술 계산을 수행하는 데 최소한의 값입니다.

나는 IC 디자인에 대해 많이 알지 못하지만 논리 게이트가 어떻게 작동하는지, 하프 가산기, 전체 가산기를 만들고, 부가들을 연결하여 다중 비트 산술을 수행하는 방법에 대해 배우는 것을 기억합니다. 그냥 확장하십시오. 많이.

자, 나는 위의 일이 작동하지 않을 것이라는 아주 좋은 이유가 있다고 확신하지만 (그렇지 않으면 내가 이미했던 것보다 많은 사람들 중 하나가 이미했던 것보다 더 똑똑한 사람들 중 하나이기 때문에) 왜 작동하지 않습니다.

(참고 :이 질문은 질문이 의미가 있는지 확실하지 않으므로 약간의 재 작업이 필요할 수 있습니다)

해결책

@cube의 말과 거대한 산술 로직 유닛이 논리 신호가 안정화되고 디지털 디자인에 다른 합병증을 포함하는 데 더 많은 시간이 걸릴 것입니다. 디지털 로직 디자인에는 소프트웨어에서 당연한 것으로 여겨지는 것, 즉 조합 논리를 통한 신호가 작지만 전파하고 정착하는 데 작은 시간이 걸립니다. 32x32 승수를 신중하게 설계해야합니다. 1024x1024 승수는 칩에서 엄청난 양의 물리적 자원을 취할뿐만 아니라 32x32 승수보다 느리게 진행됩니다 (아마도 1024x1024 곱셈을 수행하는 데 필요한 모든 부분 제품을 32x32의 승수 컴퓨팅보다 빠르지만). 또한 병목 현상 인 승수 일뿐 만 아니라 메모리 경로가 있습니다. 너비가 32 비트에 불과한 메모리 회로에서 1024 비트를 수집하고 그 결과 2048 비트를 메모리 회로에 다시 저장하는 데 많은 시간을 소비해야합니다.

거의 확실히 "기존"32 비트 또는 64 비트 시스템을 동시에 작동시키는 것이 좋습니다. 하드웨어 설계 복잡성이없는 속도를 얻습니다.

편집하다: 누구든지 ACM 액세스 권한이 있다면 (나는하지 않습니다) 이 종이 그것이 말하는 것을 보려고.

다른 팁

이 속도는 O (n)에만 있지 않지만 숫자를 고려하는 복잡성은 O (2^n) (비트 수와 관련하여)와 같은 것입니다. 따라서이 überprocessor를 만들고 숫자를 1000 배 더 빠르게 인수하면 숫자를 10 비트를 더 크게 만들면 다시 시작됩니다.

위에서 지적한 바와 같이, 주요 문제는 단순히 숫자를 고려하기 위해 얼마나 많은 가능성을 겪어야하는지입니다. 즉, 이런 종류의 일을하기 위해 전문화 된 컴퓨터가 존재합니다.

이러한 종류의 암호화의 실제 진보는 숫자 인수 알고리즘의 개선입니다. 현재 가장 빠른 알려진 일반 알고리즘은 다음과 같습니다 일반 번호 필드 체.

역사적으로, 우리는 매 10 년마다 숫자를 두 배나 큰 것으로 생각할 수있는 것 같습니다. 그 중 일부는 더 빠른 하드웨어이며, 그 중 일부는 수학에 대한 이해와 요인을 수행하는 방법입니다.

나는 언급 할 수 없다 실행할 수 있음 당신이 묘사 한 것과 똑같은 접근 방식의 접근 방식이지만 사람들은 비슷한 FPGA를 사용하여 매우 자주 사용합니다.

Shamir & Tromer 일종의를 사용하여 비슷한 접근법을 제안하십시오 그리드 컴퓨팅:

이 기사에서는 체질 단계의 맞춤형 하드웨어 구현을위한 새로운 디자인에 대해 설명하며, 이는 [Twinkle에 비해 체질 비용을 약 1,000 만 달러로 줄입니다. Twirl이라고하는 새로운 장치는 Twinkle 장치의 확장으로 볼 수 있습니다. 그러나 Twinkle과 달리 광전자 구성 요소가 없으므로 실리콘 웨이퍼의 표준 VLSI 기술을 사용하여 제조 할 수 있습니다. 근본적인 아이디어는 입력의 단일 사본을 사용하여 많은 하위 문제를 동시에 해결하는 것입니다. 입력 저장소가 비용을 지배하기 때문에, 병렬화 오버 헤드가 낮게 유지되면 결과 속도가 본질적으로 무료로 얻어집니다. 실제로, 주요 과제는 입력의 소형 저장을 허용 하면서이 병렬 처리를 효율적으로 달성하는 데 있습니다. 이를 해결하려면 숫자 이론에서 VLSI 기술에 이르기까지 수많은 고려 사항이 포함됩니다.

Uber-Quantum 컴퓨터를 만들고 실행 해보지 않겠습니까? 쇼어의 알고리즘 그 위에?

"... 충분한 수의 큐 비트를 가진 양자 컴퓨터가 구성되면 Shor의 알고리즘은 널리 사용되는 RSA 체계와 같은 공개 키 암호화 체계를 중단하는 데 사용될 수 있습니다. RSA는 많은 수의 인수가 계산적으로 불가능하다는 가정에 근거합니다. 알려진 바와 같이,이 가정은 고전적인 (Quantum이 아닌) 컴퓨터에 유효합니다. 다항식 시간을 고려할 수있는 고전적인 알고리즘은 알려져 있지 않습니다. 그러나 Shor의 알고리즘은 Quantum Computer에서 팩터링이 효율적이므로 충분히 대량의 양자 컴퓨터가 RSA를 깨뜨릴 수 있음을 보여줍니다. ... "" -wikipedia

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow