Tìm các yếu tố chính với số lượng lớn sử dụng CPU được chế tạo đặc biệt

Question

Hiểu biết của tôi là nhiều thuật toán mã hóa khóa công khai phụ thuộc vào số nguyên tố lớn để tạo nên khóa và khó khăn trong việc bao gồm sản phẩm của hai số nguyên tố mã hóa khó phá vỡ. Nó cũng là sự hiểu biết của tôi rằng một trong những lý do cho thấy số lượng lớn như vậy là rất khó, là kích thước tuyệt đối của các con số được sử dụng có nghĩa là không có CPU nào có thể hoạt động hiệu quả trên các con số, vì các CPU 32 bit và 64 bit của chúng ta không khớp cho 1024, 2048 hoặc thậm chí 4096 bit. Các thư viện toán học Big Integer chuyên dụng phải được sử dụng để xử lý các số đó và các thư viện này vốn chậm vì CPU chỉ có thể giữ (và xử lý) các khối nhỏ (như 32 hoặc 64 bit) cùng một lúc.

Vậy ...

Tại sao bạn không thể xây dựng một chip chuyên môn cao tùy chỉnh với 2048 bit, và mạch số học khổng lồ, nhiều trong cùng một cách mà chúng tôi có quy mô từ 8 đến 16 đến 32 đến 64 CPU bit, chỉ cần xây dựng một LOT một lớn hơn? Chip này sẽ không cần hầu hết các mạch trên các CPU thông thường, sau khi tất cả nó sẽ không cần phải xử lý những thứ như bộ nhớ ảo, đa luồng hoặc I/O. Nó thậm chí sẽ không cần phải là một bộ xử lý đa năng hỗ trợ hướng dẫn được lưu trữ. Chỉ cần tối thiểu để thực hiện các phép tính số học cần thiết về số ginormous.

Tôi không biết nhiều về thiết kế vi mạch, nhưng tôi nhớ tìm hiểu về cách cổng logic hoạt động, cách tạo bộ cộng một nửa, trình bổ sung đầy đủ, sau đó liên kết với nhau một nhóm người dùng để thực hiện phép tính nhiều bit . Chỉ cần mở rộng quy mô. Rất nhiều.

Bây giờ, tôi khá chắc chắn rằng có một lý do rất hay (hoặc 17) mà ở trên sẽ không hoạt động (vì nếu không một trong số nhiều người thông minh hơn tôi sẽ làm), nhưng tôi quan tâm đến việc biết lý do tại sao nó sẽ không hoạt động.

(Lưu ý: Câu hỏi này có thể cần một số lại làm việc, như tôi thậm chí không chắc chắn nhưng nếu câu hỏi có ý nghĩa)

Answer 1

Những gì @cube nói, và thực tế là một đơn vị logic số học khổng lồ sẽ mất nhiều thời gian hơn cho các tín hiệu logic để ổn định và bao gồm các biến chứng khác trong thiết kế kỹ thuật số. Thiết kế logic kỹ thuật số bao gồm một cái gì đó mà bạn cho phép trong phần mềm, cụ thể là tín hiệu thông qua logic tổ hợp có một thời gian nhỏ nhưng không phải để tuyên truyền và giải quyết. Một số nhân 32x32 cần phải được thiết kế cẩn thận. Một hệ số 1024x1024 sẽ không chỉ mất một lượng lớn tài nguyên vật lý trong một con chip, nhưng nó cũng sẽ chậm hơn một hệ số 32x32 (mặc dù có lẽ nhanh hơn một máy tính nhân 32x32 tất cả các sản phẩm một phần cần thiết để thực hiện nhân 1024x1024). Ngoài ra, nó không chỉ là hệ số nhân là nút cổ chai: bạn đã có con đường bộ nhớ.Bạn sẽ phải dành một bó thời gian thu thập 1024 bit từ một mạch bộ nhớ mà chỉ có 32 bit rộng, và lưu trữ kết quả 2048 bit trở lại vào mạch bộ nhớ.

Gần như chắc chắn sẽ tốt hơn nếu bạn có được một loạt các hệ thống 32 bit hoặc 64 bit "thông thường" hoạt động song song: bạn sẽ tăng tốc độ phức tạp của thiết kế phần cứng.

chỉnh sửa: nếu có ai có quyền truy cập ACM (tôi không), có thể hãy xem this paper để xem nội dung.

Answer 2

của nó vì tăng tốc này sẽ chỉ trong thời gian O (n), nhưng sự phức tạp của bao thanh toán số là một cái gì đó giống như O (2^n) (đối với số bit). Vì vậy, nếu bạn đã thực hiện bộ xử lý überber này và tăng số lượng 1000 lần nhanh hơn, tôi sẽ chỉ phải làm cho các con số lớn hơn 10 bit và chúng tôi sẽ trở lại bắt đầu lại.

Answer 3

Như đã nêu ở trên, vấn đề chính chỉ đơn giản là có bao nhiêu khả năng bạn phải trải qua để tạo thành một số. Điều đó đang được nói, các máy tính chuyên dụng tồn tại để làm điều này.

Tiến trình thực sự cho loại mật mã này là những cải tiến trong thuật toán bao thanh toán số. Hiện tại, thuật toán tổng quát nhanh nhất được biết đến là general number field sieve.

Trong lịch sử, chúng tôi dường như có thể nhân tố số hai lần lớn mỗi thập kỷ. Một phần của đó là phần cứng nhanh hơn, và một phần của nó đơn giản là một sự hiểu biết tốt hơn về toán học và cách thực hiện bao thanh toán.

Answer 4

Tôi không thể bình luận về tính khả thi của một cách tiếp cận chính xác như một bạn mô tả, nhưng mọi người làm tương tự những điều rất thường xuyên sử dụng FPGA:

• Crack DES keys
• Crack GSM conversations
• Open source graphics card

Answer 5

Tại sao don ' bạn thử xây dựng một máy tính uber-lượng tử và chạy Shor's algorithm trên nó?

" ... Nếu một máy tính lượng tử có đủ số qubit đã được xây dựng, thuật toán Shor của thể được sử dụng để phá vỡ các chương trình mật mã hóa khóa công khai như chương trình RSA sử dụng rộng rãi. RSA dựa Cho đến nay được biết, giả định này là hợp lệ cho các máy tính cổ điển (không phải lượng tử), không có thuật toán cổ điển nào được biết là có thể nhân tố trong thời gian đa thức. hiệu quả trên máy tính lượng tử, do đó, một máy tính lượng tử đủ lớn có thể phá vỡ RSA. ... "-Wikipedia

Answer 6

Shamir & Tromer đề nghị một phương pháp tương tự, sử dụng một loại grid computing:

Bài viết này thảo luận về một thiết kế mới cho việc thực hiện phần cứng tùy chỉnh của bước sàng, mà giảm [chi phí sàng, tương đối đến TWINKLE,] khoảng 10 triệu đô la. Thiết bị mới, được gọi là TWIRL, có thể được xem là phần mở rộng của thiết bị TWINKLE. Tuy nhiên, không giống như TWINKLE nó không có các thành phần quang điện tử, và có thể do đó được sản xuất bằng công nghệ VLSI tiêu chuẩn trên tấm silicon. Ý tưởng cơ bản là sử dụng một bản sao đầu vào để giải quyết nhiều bài toán con song song. Vì dung lượng lưu trữ đầu vào chiếm ưu thế chi phí, nếu chi phí song song được giữ ở mức thấp thì kết quả là tốc độ được lấy về cơ bản miễn phí. Thật vậy, thách thức chính nằm trong việc đạt được tính song song này một cách hiệu quả trong khi cho phép lưu trữ nhỏ gọn đầu vào. Việc giải quyết vấn đề này liên quan đến việc cân nhắc vô số, từ từ lý thuyết số tới công nghệ VLSI.