Going as fast as possible in Rust
An in-depth look at optimizing the Quadratic Sieve for factoring
Dr. Christopher Swenson is a programmer who is passionate about open source, mathematics, cryptography, sorting, and cats. Christopher wrote the book Modern Cryptanalysis in 2008. He has worked for Google, Twilio, HashiCorp, the US Government, and others.
The Quadratic Sieve is one of the fastest algorithms for factoring numbers. The gold standard implementation was written in C for x86 processors almost 20 years ago.
Let's talk about how we'd implement it today in Rust, the gold standard of low-level languages here in 2023.
We'll start with a short outline of the quadratic sieve steps -- don't worry, only basic algebra is required to understand the algorithm and our talk. Then we'll dive deep for the main portion of the talk: performance optimization in Rust.
And then we'll dive into some fun optimization areas:
- What benefits do Rust and LLVM give us?
- What are the disadvantages of Rust over C for this, and what can we do about them?
- What do we have to do to get similar performance to a 20-year-old C program?
- How do we take advantage of modern processor features like AVX and NEON?
- Should we use Rust inline assembly to close the gap?
- Should we implement the algorithm differently in Rust or for modern processors?
- Date:
- 2023 November 4 - 10:30
- Duration:
- 50 min
- Room:
- Room 1
- Conference:
- SeaGL 2023
- Language:
- Track:
- Languages and Tools
- Difficulty:
- Intermediate
- Distributed Authorization with CAProck
- Start Time:
- 2023 November 4 10:30
- Room:
- Room 3
- Secure Coding: Fix from the root
- Start Time:
- 2023 November 4 10:30
- Room:
- Room 2
- Effective git code review - make their job easier and you look smarter
- Start Time:
- 2023 November 4 10:30
- Room:
- Room 4
- What's the Ideal Give-Away Computer?
- Start Time:
- 2023 November 4 11:00
- Room:
- Room 4