# Review Of Integrated Photonic Elastic WDM Switches For Data Centers

Akhilesh S P Khope
Microsoft Corporation
One Microsoft Way
Redmond, WA, 98052
<EMAIL_ADDRESS>
Anirban Samanta, Xian Xiao, Ben Yoo
Department of Electrical And Computer Engineering
One Shields Avenue, Kemper Hall
University of California
Davis, CA 95616

John E Bowers
Department of Electrical And Computer Engineering
University of California
Santa Barbara, CA, 93106

###### Abstract

In this review paper, we present an elaborate discussion on wavelength
selective switches and their demonstrations. We also review packaging and
electronic photonic integration of switches; a topic neglected in other review
papers. We also cover wavelength locking which is paramount in switching
networks with many tunable filters.

_Keywords_ Switching $\cdot$ Silicon Photonics $\cdot$ Photonic Integrated
Circuits

##  1 Introduction

Switch is a device used to turn off and on a connection between two ports. If
N terminal devices like telephones or computer servers are connected to each
other, switch can reduce the number of connections from $N(N-1)$ to $2N$ and
also intelligently provision bandwidth according to demand. One of the first
demonstrations of a crossbar switch was in 1915 Craft and Reynolds (1915), the
switch was an electromechanical switch used for switching telephone calls.
Widespread use of crossbar switches is reported in Sweden in 1926 and later in
1938 in AT&T Bell Labs.

Larger port count switches are hard to manufacture and thus Charles Clos
created an ingenious way of creating a bigger network from smaller switches in
1953 Clos (1953). Many datacenter architectures follow a modified version of
this architecture called fat tree topology. Switching networks as well as
switches which form them can be either blocking, strictly non blocking or
reconfigurable non blocking. For a detailed discussion on this, reader is
advised to read Beneš (1965). In this paper, many of the integrated photonic
switches reported are rearrangeably non-blocking as their configuration
changes according to an arbitrator on a global clock. With the miniaturization
of devices in Silicon Photonics, advances in lasers and Semiconductor Optical
Amplifiers (SOAs) in III-V platforms and tight electronic and photonic
integration through fabless photonic foundries it is now possible to fabricate
and integrate larger port count switching networks on a single chip.

The communication patterns in the today’s high performance computing and
datacenter systems are spatially and temporally non-uniform, which means the
bursty bandwidth requirement in some data links could cause heavy congestion.
However, today’s electronic switches based interconnections have a fixed
topology, which is incapable of dynamically adapting the bandwidth to the
workloads. In recent years, several optical bandwidth-reconfigurable switching
fabrics have been demonstrated by using wavelength-and-space selective optical
switches. By utilizing wavelength division multiplexing (WDM) technologies,
such switches can achieve bandwidth steering by reconfiguring the number of
wavelength channels in selected pairs of nodes while maintaining the benefit
of optical switching, including higher speed and lower power consumption.

Architecture of most of the switches reported in this review consists of a
wavelength division multiplexed (WDM) signal at the input of an integrated
photonic switch and a receiver with a demux. Integrated photonic switches can
be categorized into broadband/fiber switches and wavelength selective switches
(WSS). Wavelength selective switches can be further categorized into single
wavelength selective and elastic/multiwavelength selective switches. In
broadband switches, the entire WDM signal from one port is switched to another
port. In single wavelength selective switches connection between ports has
only one wavelength connection between ports, and if one changes the input
wavelength at input port the signal is received at a different output port. In
elastic/multiwavelength selective switch, different ports can be connected to
each other using one or more than one wavelength from the WDM signal.

In the following two paragraphs, we report some data center architectures with
WSS from literature. Such switches can be integrated into datacenter networks
and high performance computing clusters with some modification. Fig. 1(a)
shows a data center network with multi degree WSS mesh connecting different
server groups reported by Google in Zhao et al. (2016). The optical switches
in the WSS mesh can increase network scalability and result in fewer physical
links between elements of the data center network which results in reduced
hardware and network cost. Fig. 1(b) shows a datacenter architecture with WSS
in a multidimentional interconnection network called Hyper-X is reported in
Saleh et al. (2016). Hyper-X requires very dense fiber connections for large
radix HPC and datacenter networks and the induction of WSS switches enables
reconfigurability and results in simplifying wiring.

Fig. 1(c) shows a method of designing networks based on AWGs and WSSs is
reported in Lin and Lea (2017). This method is more flexible in terms of
construction of different switch sizes. Another method for constructing such
networks is reported by the same group in Huang and Lea (2016). Fig. 1(d)
shows a switch with broadband photonic switch and WSS for switching between
top of the rack switches is reported in Xu et al. (2011). Fig. 1(e) shows an
AWGR based architecture for datacenters (citation). Fig. 1(f) shows an Optical
Top Of the Rack (OTOR) architecture that can be integrated into a software
defined network (SDN) enabled datacenter architecture with dynamic bandwidth
allocation using WSS Xue et al. (2020). Fig. 1(g) shows application of IRIS
WSS used as a transponder aggregator for Reconfigurable Optical Add Drop
Multiplexers (ROADMs) Testa et al. (2018).

Figure 1: (a) check this again , Dynamic datacenter network with Multi-Degree
WSS mesh, (b) HyperX topology for WSS (bigger) , (c) Non-blocking wavelength
space switches with WSSs Lin and Lea (2017), (d) switching between top of the
rack switches, (e) application of AWGR based switches in datacenters, (f)
photonic top of the rack switch (g) application of IRIS WSS ROADMs  Figure 2:
(a) 8x4 switch reported in Khope et al. (2019), (b) 8x8 SOA based switch
reported in Stabile et al. (2013), (c) Flex lions based switch reported in
Xiao et al. (2019), (d) Reconfigurable silicon photonic ROADM is reported in
Testa et al. (2016, 2018), (e) $8\times 8\times 8$ SiP MEMS switch is reported
in Seok et al. (2019)

There have been numerous reviews on photonic switching and datacenter
technologies Cheng et al. (2018a); Lee (2017); Shen et al. (2019); Cheng et
al. (2018b), none of them have covered integrated photonic elastic WDM
switches.

The main difference between our paper and the other recently published review
papers is:

  1. 1.

we do an in depth review of integrated photonic elastic WDM switches as
compared to other papers.

  2. 2.

we do an in depth review of packaging and integration of the switches with
electronics.

  3. 3.

we also cover wavelength locking and stabilization.

In Section II of this review, we review integrated photonic architectures. In
Section III, we compare different switching devices. In Section IV, we review
demonstrations of wavelength selective switches. In Section VI, we discuss
packaging technologies for both broadband and WSS. In Section VII, we discuss
wavelength locking and stabilization.

##  2 Architectures

Smaller switches can be arranged in different architectures according to
application. WSS can be arranged in the following architectures (Maybe
diagram):

  * •

Layered architecture

  * •

Crossbar

  * •

AWGR based switches

All switching architectures have N input ports , an output ports and M
wavelengths at each input.

Crossbar switch: In this arrangement there are upto M ring resonators at each
intersection. There are $MN^{2}$ switching elements. Optical path loss is path
dependent.

Layered switch : In this arrangement, N demultiplexers routes M wavelengths to
M $N\times N$ single wavelength switches and these are connected to N
multiplexers. Single wavelength switches in this arrangement can be AWGRs,
Crossbar switches, Benes switches and any other non blocking switching
arrangement. This type of switch can be built in a silicon photonic platform
or III-V platform using SOAs. There are $MN^{2}$ switching elements if using
crossbar as a switching element. $M+2N$ switching elements if using cyclic
AWGRs, multiplexer and demultiplexer .$MNlogN$ switching elements is a Benes
network is used.Authors in Wagner et al. (1996) reported MONET, a layered
switch for metro and long haul networks.

AWGR based architecture: In this arrangement, M tunable lasers are used at
each N ports. A cyclic AWGR is used to route wavelengths to different ports
based on the input wavelength from tunable lasers. There are $2MN$ active
elements (tunable lasers).

##  3 Demonstration of switches

In multi-wavelength switches, in addition to all to all extra connections can
be provisioned between nodes as per demand. This reconfiguration provides
superior latency when load is higher as compared to fixed connectivity all to
all switches. These switches also require a control plane for arbitration.
Multi-wavelength crossbar MRR based switches fabricated in silicon photonics
foundries are reported in Khope et al. (2017a, 2019). The authors switch in
Khope et al. (2016) and we carry out architectural exploration in Saleh et al.
(2016). These switches have upto two wavelength connectivity per connection
and provide latency comparable to that of full wavelength connectivity. Cyclic
Arrayed Waveguide Grating Router (AWGR) based switches are reported in Flex
Lions Xiao et al. (2020). These family of switches use two FSRs of the AWGR,
to provide multi-wavelength connectivity. Fully flexible switches are reported
in MRR based Benes network Goebuchi et al. (2008) and a layered wavelength
selective 8x8x8 MEMS switch reported in Seok et al. (2018). A switch and
select switch is reported in Polarization-Diversity MRR based switch fabric
Yang et al. (2020). A crossbar switch capable of joint unicast and multi-cast
functionality is reported in Su et al. (2015). In this switch architecture an
all to all connectivity is provided by partial drop MRR and full connectivity
is provided on demand by a full power drop MRR. A 2x2 2 channel WSS with
unlimited free spectral range using contra directional grating couplers is
reported in Ikeda et al. (2020). A multicast and multi wavelength selective
switch is reported Khope et al. (2021a, b). Multi-wavelength selective switch
experiments are also reported in Khope et al. (2020). Push—pull microring-
assisted space-and-wavelength selective switch crossbar switch is reported in
Huang et al. (2020).

A $1\times 2$ WSS MRR based on nested pairs of subrings is demonstrated in Wu
et al. (2015). A $1\times 2$ wavefront control type WSS was reported using
silicon waveguides in Nakamura et al. (2018a). A $2\times 2$ WSS with four
wavelength channels, thermo optic MZ switches and MRRs with a wavelength
transmittance change of 9.7 dB is reported in Miura et al. (2012). A silicon
based $1\times 2$ WSS with foldback AWG is reported in Nakamura et al.
(2018b). A $4\times 4\times 4$ hitless MRR based non blocking switch is
reported in Goebuchi et al. (2008). A monolithic $1\times 2$ WSS gridless
switch in silicon and silicon nitride waveguides is reported in Doerr et al.
(2011). A 200 GHz, 17 channel $1\times 2$ SiP WSS with AWG loopback is
reported in Asakura et al. (2015). This switch reported losses from 21 dB to
26 dB and a crosstalk range of -21 to -2 dB. A flexible grid $1\times 2$ WSS
in SiP with 9 MRR is reported in Wang et al. (2017) with a crosstalk lower
than -11.5 dB and a maximum tuning bandwidth of 4.09 nm.

A 2x2 microring based WSS is reported in Xu et al. (2011); Lira et al. (2009).
A scalable 2x2 crossbar silicon photonic switch is reported in Li et al.
(2015). A SiP mode and wavelength switch is reported in Velha et al. (2015). A
high speed 2x2 SiP multi-wavelength switch is reported in Lee et al. (2009),
maybe similar paper Lee et al. (2008). A MRR based cascaded SiP ring crossbar
switch is reported in Poon et al. (2008). An AWGR based WSS is reported in Yu
et al. (2013). A slow light based WSS using photonic crystals is reported in
Beggs et al. (2008). A thermo optic photonic crystal based switch 2x2 is
reported in Zhou et al. (2017).Wavelength-selective $2\times 2$ optical switch
based on a Ge2Sb2Te 5-assisted microring Zhang et al. (2020). A $2\times
2\times 2\lambda$ switch is reported in Huang et al. (2020). A layered switch
with switch and select stages is proposed in Cheng et al. (2019).

InP based switches have a larger footprint for the same switch radix and are
typically built using SOAs. These switches can have zero net optical loss. A
8x8 wavelength and space cross-connect is reported in InGaAsP/InP platform
with $1\times 8$ broadband selection stages and $8\times 8$ gated cyclic
routers in Stabile et al. (2013). A $1\times 8$ optical module of a $8\times
8\times 8\lambda$ wavelength selective switch and select architecuture with
SOAs in InP is reported in Prifti et al. (2018). SiP switches with integrated
SOAs can provide zero optical path loss and are reported in Konoike et al.
(2018). A tunable 2x2 WSS in SiO2-Si3N4 is reported in Geuzebroek et al.
(2005). AWGR in flex lions is on top of silicon.

##  4 Packaging

Packaging of photonic circuits requires consideration of optical, electrical,
thermal and mechanical challenges of integrating photonic circuits to off-chip
interfaces. In terms of signal transmission the two main domains are the
optical fiber-to-waveguide coupling and integration with electronics.

Figure 3: (a) Switch die integrated onto a PCB with overhang for edge coupling
as reported in Khope et al. (2019), (b) MEMS switch flip-chip packaged on a
ceramic package reported in Hwang et al. (2017a), (c) SiPh switch die
wirebonded in a CBGA package reported in Dumais et al. (2017), (d) Switch die
mounted on a PCB with control electronics reported in Suzuki et al. (2019),
(e) Switch PIC with grating couplers for vertical coupling of light reported
in Testa et al. (2018), (f) A transponder system with switch module packaged
with fiber array reported in Nakamura et al. (2016), (g) Monolithic photonic
switch system-on-chip reported in Lee et al. (2013), (h) CMOS driver IC flip-
chip bonded onto photonic chip for 3D vertical integration as reported in
Rylyakov et al. (2011), (i) Heterogeneous integration of CMOS die into a
cavity of a PIC die followed by further processing to establish metallic
contacts as reported in Chen et al. (2013), (j) A pluggable SiPh switch
concept reported in Hwang et al. (2018), (k) Monolithic integration of active
photonic devices reported in Atabaki et al. (2018), (l) Through-oxide via
(TOV) technology for vertical integration of electronic interconnect and (m)
Backside processing of flipped photonic die to form TOVs reported in Settaluri
et al. (2015) and Stojanović et al. (2015)

###  4.1 Fiber-to-waveguide Coupling

####  4.1.1 Grating Coupler

A Bragg diffraction grating structure of periodic or chirped design is
utilized to vertically couple light to and from an off-chip fiber, making this
technique wavelength dependent, resulting in narrow bandwidth, wavelength and
polarization sensitivity. They tend to be compact, have high alignment
tolerance, simpler wafer-scale testing and high volume manufacturing.
Fabricated grating couplers with more than 70% measured coupling efficiency
have been demonstrated Marchetti et al. (2017), Kang et al. (2020).

####  4.1.2 Edge Coupler and Evanescent Coupler

An edge coupler consists of an inverse taper section where the waveguide width
is gradually reduced to a fine tip. As the guided wave propagates along the
taper, it becomes less confined and it’s effective cross-section increases.
The expanded wave can then be coupled into a lensed fiber. Edge coupling can
be more efficient than grating couplers, with up to 90% efficiency Takei et
al. (2013), however they require highly polished facets to achieve high
efficiency necessitating complex fabrication processes. Usually long tapers
are required for adiabatic functioning, and they also suffer from mode
mismatch challenges. Evanescent coupler is an extension of the edge coupling
concept. Instead of coupling light into a fiber at the edge, the expanded mode
is coupled into another tapered waveguide fabricated in another PIC or
interposer with optical fibers pre-attached Dangel et al. (2015). It offers
the advantages of edge coupling along with relaxed alignment tolerances
characteristic of grating couplers.

###  4.2 Electronic Packaging

Photonic circuits need to be driven by electronics and the high speed nature
of the signals require careful design of the electrical interconnect in order
to control the impedance values and electrical crosstalk. Electrical pads on
photonic chips are connected to electrical pads on driver asics, and these
connections are finally connected to the PCB. The pad pitch of both photonic
and electronic chips is much smaller than pad pitch of PCB. The mismatch in
pitch between PCB and chip can be circumvented by using an intermediary
interposer or package with an organic or ceramic ball grid array (BGA). The
interconnection is usually done with wire bonds or through vertical
integration methods.

####  4.2.1 Wire bonding

If the number of electrical connections is low (typically less than 400), wire
bonding offers a simple solution where bare metal wires are used to connect
PIC contact pads on the top surface to a leadframe on an organic or ceramic
BGA package Dumais et al. (2018). These packages typically support $150\,\mu
m$ or more in contact pitch with the backside ball grid array pitch being 0.5
mm or more. Wire bonds tend to have higher impedance values limiting
electrical performance.

####  4.2.2 Vertical integration

When a large number of contacts, dense electrical I/O or higher electrical
performance is necessary, vertical integration becomes critical. Vertical
integration with flip-chip bonding or by using through silicon vias (TSVs) and
through oxide vias (TOVs) can reduce the length of electrical interconnect to
the order of the IC thickness (100s of $\mu m$) compared to many millimeters
in wire-bonded solutions, reducing the parasitic impedance Settaluri et al.
(2015) allowing for improved performance. In a flip-chip solution, the IC die
is flipped with C4 solder bumps or copper pillars used to attach to a
traditional organic or ceramic package. However when access to the active side
of the die is necessary, for example when using grating couplers, flip-chip
bonding may not be possible. In such cases vertical integration is made
possible by using TSVs/TOVs where a via is formed through the bulk silicon or
oxide from the inner contact pad to a backside metal pad for C4 or copper
pillar bonding Bogaerts et al. (2018).

An 8$\times$8 SiPh Flex-LIONS chip with with 176 electrical pads is wire-
bonded to a co-designed printed circuit board (PCB) for electrical fan-out
[35]. Two lid-less 16-channel 127-µm-pitch polarization-maintaining (PM) fiber
arrays are attached to the input and output of the chip using index-matching
UV epoxy. Flexible flat cable (FFC) connectors are surface-mounted on the PCB
for a compact footprint.

A pluggable SiP MEMS switch array has been demonstrated with contact
interposer and ceramic interposer in Hwang et al. (2018). A $128\times 128$
MEMS switch with glass interposer and pitch reducing fiber array is
demonstrated in Hwang et al. (2017b). A flip chip packaging of a $12\times 12$
switch using via less ceramic interposer is reported in Hwang et al. (2017a).
A $32\times 32$ switch with thermo optic MZI and monolithic monitor
photodiodes is wirebonded to a CBGA with 68 fiber ribbon in Dumais et al.
(2017).

A $32\times 32$ switch with an extremely high-$\Delta$-PLC connector is
demonstrated in Suzuki et al. (2019).A $32\times 32$ non duplicate
polarization diversity switch is reported in Suzuki et al. (2020). In this
paper, authors report switch flip chip bonded to a ceramic interposer that
converts 0.18 mm pitch electrodes with 0.5 mm Land Grid Array (LGA), and a 74
port $127\,\mu m$ fiber array was attached to the chip.

A 3D integrated photonic and electronic chip using $50\,\mu m$ copper pillar
technology is reported in Testa et al. (2018).

An $8\times 8$ MZI based switch with a submount packaged with 16 narrow core
fiber array with SMF on the other side and Spot Size Converter (SSC) on the
chip is reported in Nakamura et al. (2016). In the same work, authors also
report transponder aggregators (TPAs) assembly with 12 co-packaged optical
switch modules with current drivers for 1800 thermo optic heaters.

Hybrid packaging of SiP switches, electronic driver chip and SOA arrays flip
chip attached to a silicon carrier is reported in Budd et al. (2015). A
12-channel SMF ribbon to chip assembly performed using high-volume tooling
with off the shelf components is reported in Lee and Dupuis (2018). A fully
integrated $4\times 4$ switch flip chip integrated with a CMOS driver IC is
reported in Rylyakov et al. (2011). A broadband $2\times 2$ MZI switch is
wirebonded to an electronic asic in Lee et al. (2013). An FPGA embeded system
with 16 high speed DAC/ADC and a packaged 4x4 silicon benes switch is reported
in Huang et al. (2017).A 2 × 2 Mach-Zehnder interferometer (MZI)-based switch
element (SE) with active feedback power equalization fabricated in a wafer-
scale hybrid silicon process is reported in Chen et al. (2013).

65 nm transistor bulk silicon CMOS technology with a layer of poly-crystalline
silicon for photonic devices in a 300 millimeter wafer microelectronics
foundry is reported in Atabaki et al. (2018). A zero change process in 32 nm
and 45 nm SOI CMOS with both transistors and photonic devices is reported in
Stojanović et al. (2018). A process in which SOI wafer is oxide bonded face-
to-face with the CMOS wafer with Through oxide vias with 3fF parasitic
capacitance up to 10x lower than that of micro-bump/copper pillar connection
is reported in Stojanović et al. (2015). A 4x4 switch with IBM’s 90nm
photonics-enabled CMOS process is reported in Dupuis (2016).

##  5 Wavelength locking and stabilization

Switching elements used in WSS are sensitive to temperature variation and also
have to be operated very close to servers in datacenters. Various wavelength
locking and stabilization techniques have been reported for MRRs. A feedback
control mechanism, based on ContactLess Integrated Photonic Probes and heater
actuators, is used to monitor and lock each device in real-time in Zanetto et
al. (2020). For multi-wavelength selective crossbar switches, a locking
technique which uses heaters in monitor partial power drop ring resonators for
calibration is reported in Khope et al. (2017a, b). In the paper, authors lock
two wavelength channels simultaneously from $20-40^{\circ}C$. Hitless tuning
of MRR using a novel channel labelling scheme is reported in Aguiar et al.
(2018). A demonstration of locking with photoconductive heaters is reported in
Jayatilleka et al. (2019). Locking of three rings with a single monitor signal
over a temperature range of $>40^{\circ}C$ at 3x20 Gb/s OOK modulation and
3x75 Gb/s discrete multi-tone (DMT) modulation is reported in Dong et al.
(2017). An FPGA based tuning algorithm for WDM applications is reported in
Gazman et al. (2017). A wavelength stabilization scheme for silicon MRR with
an in-resonator defect-state-absorption-based photodetector is reported in Li
and Poon (2015). A non invasive monitoring scheme using cmos integrated
electronics is reported in Grillanda et al. (2014). A locking scheme based
dithering of heater voltage is reported in Padmaraju et al. (2013). An
automated wavelength allignment of a $5^{th}$ order MRR with negligible
passband ripples is reported in Mak et al. (2015). Automatic calibration of
4x4 Benes is reported in siliconHuang et al. (2017).

##  6 Conclusion

We summarize the work done on integrated photonic WSS and their applications
in datacenters. Electronic and photonic integration has enabled bigger
switches with more complicated conntrol circuits. Currently nunmber of ports
and number of wavelengths supported are limited by the size of electrical
pads. With improvements in packaging technology and fabrication processes, we
envision WSS with higher port counts.

## References

  * Craft and Reynolds [1915] Edward B Craft and John N Reynolds.  Multiple-brush selector., January 5 1915.  US Patent 1,123,695.
  * Clos [1953] Charles Clos.  A study of non-blocking switching networks.  _Bell System Technical Journal_ , 32(2):406–424, 1953.
  * Beneš [1965] Václav E Beneš.  _Mathematical theory of connecting networks and telephone traffic_.  Academic press, 1965.
  * Zhao et al. [2016] Xiaoxue Zhao, Bikash Koley, and Amin Vahdat.  Dynamic data center network with a mesh of wavelength selective switches, November 8 2016.  US Patent 9,491,526.
  * Saleh et al. [2016] Adel AM Saleh, Akhilesh SP Khope, John E Bowers, and Rod C Alferness.  Elastic wdm switching for scalable data center and hpc interconnect networks.  In _2016 21st OptoElectronics and Communications Conference (OECC) held jointly with 2016 International Conference on Photonics in Switching (PS)_ , pages 1–3. IEEE, 2016.
  * Lin and Lea [2017] Bey-Chi Lin and Chin-Tau Lea.  Construction of nonblocking wavelength/space switches with awgs and wsses.  _Applied Sciences_ , 7(6):555, 2017.
  * Huang and Lea [2016] Yifan Huang and Chin-Tau Lea.  A new wss-based optical network architecture for data center networks.  In _2016 Photonics North (PN)_ , pages 1–1. IEEE, 2016.
  * Xu et al. [2011] Lin Xu, Wenjia Zhang, Hugo LR Lira, Michal Lipson, and Keren Bergman.  A hybrid optical packet and wavelength selective switching platform for high-performance data center networks.  _Optics Express_ , 19(24):24258–24267, 2011.
  * Xue et al. [2020] Xuwei Xue, Fumi Nakamura, Kristif Prifti, Bitao Pan, Fulong Yan, Fu Wang, Xiaotao Guo, Hiroyuki Tsuda, and Nicola Calabretta.  Sdn enabled flexible optical data center network with dynamic bandwidth allocation based on photonic integrated wavelength selective switch.  _Optics Express_ , 28(6):8949–8958, 2020.
  * Testa et al. [2018] Francesco Testa, Stefano Tondini, Fabrizio Gambini, Philippe Velha, Alberto Bianchi, Christophe Kopp, Michael Hofbauer, Costanza Lucia Manganelli, Nikola Zecevic, Stefano Faralli, et al.  Integrated reconfigurable silicon photonics switch matrix in iris project: Technological achievements and experimental results.  _Journal of Lightwave Technology_ , 37(2):345–355, 2018.
  * Khope et al. [2019] Akhilesh SP Khope, Mitra Saeidi, Raymond Yu, Xinru Wu, Andrew M Netherton, Yuan Liu, Zeyu Zhang, Yujie Xia, Garey Fleeman, Alexander Spott, et al.  Multi-wavelength selective crossbar switch.  _Optics express_ , 27(4):5203–5216, 2019.
  * Stabile et al. [2013] R Stabile, A Rohit, and KA Williams.  Monolithically integrated 8$\times$ 8 space and wavelength selective cross-connect.  _Journal of Lightwave Technology_ , 32(2):201–207, 2013.
  * Xiao et al. [2019] Xian Xiao, Roberto Proietti, Sebastian Werner, Pouya Fotouhi, and SJ Ben Yoo.  Flex-lions: A scalable silicon photonic bandwidth-reconfigurable optical switch fabric.  pages 1–3, 2019.
  * Testa et al. [2016] Francesco Testa, Claudio J Oton, Christophe Kopp, Jong-Moo Lee, Ruben Ortuno, Reinhard Enne, Stefano Tondini, Guido Chiaretti, Alberto Bianchi, Paolo Pintus, et al.  Design and implementation of an integrated reconfigurable silicon photonics switch matrix in iris project.  _IEEE Journal of Selected Topics in Quantum Electronics_ , 22(6):155–168, 2016.
  * Seok et al. [2019] Tae Joon Seok, Jianheng Luo, Zhilei Huang, Kyungmok Kwon, Johannes Henriksson, John Jacobs, Lane Ochikubo, Richard S Muller, and Ming C Wu.  Silicon photonic wavelength cross-connect with integrated mems switching.  _APL Photonics_ , 4(10):100803, 2019.
  * Cheng et al. [2018a] Qixiang Cheng, Meisam Bahadori, Madeleine Glick, Sébastien Rumley, and Keren Bergman.  Recent advances in optical technologies for data centers: a review.  _Optica_ , 5(11):1354–1370, 2018a.
  * Lee [2017] Benjamin G Lee.  Silicon photonic switching: Technology and architecture.  In _2017 European Conference on Optical Communication (ECOC)_ , pages 1–3. IEEE, 2017.
  * Shen et al. [2019] Yiwen Shen, Xiang Meng, Qixiang Cheng, Sébastien Rumley, Nathan Abrams, Alexander Gazman, Evgeny Manzhosov, Madeleine Strom Glick, and Keren Bergman.  Silicon photonics for extreme scale systems.  _Journal of Lightwave Technology_ , 37(2):245–259, 2019.
  * Cheng et al. [2018b] Qixiang Cheng, Sébastien Rumley, Meisam Bahadori, and Keren Bergman.  Photonic switching in high performance datacenters.  _Optics express_ , 26(12):16022–16043, 2018b.
  * Wagner et al. [1996] Richard E Wagner, Rod C Alferness, AAM Saleh, and Matthew S Goodman.  Monet: Multiwavelength optical networking.  _Journal of Lightwave Technology_ , 14(6):1349–1355, 1996.
  * Khope et al. [2017a] Akhilesh SP Khope, Takako Hirokawa, Andrew M Netherton, Mitra Saeidi, Yujie Xia, Nicolas Volet, Clint Schow, Roger Helkey, Luke Theogarajan, Adel AM Saleh, et al.  On-chip wavelength locking for photonic switches.  _Optics letters_ , 42(23):4934–4937, 2017a.
  * Khope et al. [2016] Akhilesh SP Khope, Adel AM Saleh, John E Bowers, and Rod C Alferness.  Elastic wdm crossbar switch for data centers.  In _2016 IEEE Optical Interconnects Conference (OI)_ , pages 48–49. IEEE, 2016.
  * Xiao et al. [2020] X. Xiao, R. Proietti, G. Liu, H. Lu, Y. Zhang, and S. J. B. Yoo.  Multi-fsr silicon photonic flex-lions module for bandwidth-reconfigurable all-to-all optical interconnects.  _Journal of Lightwave Technology_ , 38(12):3200–3208, 2020.
  * Goebuchi et al. [2008] Yuta Goebuchi, Masahiko Hisada, Tomoyuki Kato, and Yasuo Kokubun.  Optical cross-connect circuit using hitless wavelength selective switch.  _Optics express_ , 16(2):535–548, 2008.
  * Seok et al. [2018] Tae Joon Seok, Jianheng Luo, Zhilei Huang, Kyungmok Kwon, Johannes Henriksson, John Jacobs, Lane Ochikubo, Richard S Muller, and Ming C Wu.  Mems-actuated 8$\times$ 8 silicon photonic wavelength-selective switches with 8 wavelength channels.  In _2018 Conference on Lasers and Electro-Optics (CLEO)_ , pages 1–2. IEEE, 2018.
  * Yang et al. [2020] Hao Yang, Qixiang Cheng, Rui Chen, and Keren Bergman.  Polarization-diversity microring-based optical switch fabric in a switch-and-select architecture.  pages Th3B–2, 2020.
  * Su et al. [2015] Zhan Su, Erman Timurdogan, Michele Moresco, Gerald Leake, Douglas D Coolbaugh, and Michael R Watts.  Wavelength routing and multicasting network in ring-based integrated photonics.  In _Integrated Photonics Research, Silicon and Nanophotonics_ , pages IT4A–3. Optical Society of America, 2015.
  * Ikeda et al. [2020] Kazuhiro Ikeda, Keijiro Suzuki, Ryotaro Konoike, and Hitoshi Kawashima.  Silicon photonics wavelength selective switch with unlimited free spectral range.  _Journal of Lightwave Technology_ , 2020.
  * Khope et al. [2021a] Akhilesh SP Khope, Roger Helkey, Songtao Liu, Sairaj Khope, Rod C Alferness, Adel AM Saleh, and John E Bowers.  Scalable multicast hybrid broadband-crossbar wavelength selective switch: proposal and analysis.  _Optics Letters_ , 46(2):448–451, 2021a.
  * Khope et al. [2021b] Akhilesh S. P. Khope, Roger Helkey, Songtao Liu, Adel A. M. Saleh, Rod C. Alferness, and John E. Bowers.  A scalable multicast hybrid broadband crossbar wavelength selective switch for datacenters.  In _2021 IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC)_ , pages 1585–1587, 2021b.  doi:10.1109/CCWC51732.2021.9376020.
  * Khope et al. [2020] Akhilesh S.P. Khope, Songtao Liu, Andy Netherton, Zeyu Zhang, Sairaj Khope, Roger Helkey, Adel A.M. Saleh, Rod C. Alferness, and John E. Bowers.  Experiments on multiwavelength selective crossbar switches.  In _2020 International Conference on Information Science and Communications Technologies (ICISCT)_ , pages 1–5, 2020.  doi:10.1109/ICISCT50599.2020.9351493.
  * Huang et al. [2020] Yishen Huang, Qixiang Cheng, Anthony Rizzo, and Keren Bergman.  Push—pull microring-assisted space-and-wavelength selective switch.  _Optics Letters_ , 45(10):2696–2699, 2020.
  * Wu et al. [2015] Jiayang Wu, Pan Cao, Ting Pan, Yuxing Yang, Ciyuan Qiu, Christine Tremblay, and Yikai Su.  Compact on-chip 1$\times$ 2 wavelength selective switch based on silicon microring resonator with nested pairs of subrings.  _Photonics Research_ , 3(1):9–14, 2015.
  * Nakamura et al. [2018a] Fumi Nakamura, Kyosuke Muramatsu, Keijiro Suzuki, Ken Tanizawa, Minoru Ohtsuka, Nobuyuki Yokoyama, Kazuyuki Matsumaro, Miyoshi Seki, Keiji Koshino, Kazuhiro Ikeda, Shu Namiki, Hitoshi Kawashima, and Hiroyuki Tsuda.  Integrated silicon photonic wavelength-selective switch using wavefront control waveguides.  _Opt. Express_ , 26(10):13573–13589, May 2018a.  doi:10.1364/OE.26.013573.  URL http://www.opticsexpress.org/abstract.cfm?URI=oe-26-10-13573.
  * Miura et al. [2012] Kengo Miura, Yuya Shoji, and Tetsuya Mizumoto.  Silicon waveguide wavelength-selective switch for on-chip wdm communications.  In _IEEE Photonics Conference 2012_ , pages 630–631. IEEE, 2012.
  * Nakamura et al. [2018b] Fumi Nakamura, Hideaki Asakura, Keijiro Suzuki, Ken Tanizawa, Minoru Ohtsuka, Nobuyuki Yokoyama, Kazuyuki Matsumaro, Miyoshi Seki, Keiji Koshino, Kazuhiro Ikeda, et al.  Silicon photonics based 1$\times$ 2 wavelength selective switch using fold-back arrayed-waveguide gratings.  _IEICE Electronics Express_ , 15(14):20180532–20180532, 2018b.
  * Doerr et al. [2011] CR Doerr, LL Buhl, L Chen, and N Dupuis.  Monolithic gridless $1\times 2$ wavelength-selective switch in silicon.  In _Optical Fiber Communication Conference_ , page PDPC4. Optical Society of America, 2011.
  * Asakura et al. [2015] Hideaki Asakura, Takemasa Yoshida, Hiroyuki Tsuda, Keijiro Suzuki, Ken Tanizawa, Munehiro Toyama, Minoru Ohtsuka, Nobuyuki Yokoyama, Kazuyuki Matsumaro, Miyoshi Seki, et al.  A 200-ghz spacing, 17-channel, 1$\times$ 2 wavelength selective switch using a silicon arrayed-waveguide grating with loopback.  In _2015 International Conference on Photonics in Switching (PS)_ , pages 52–54. IEEE, 2015.
  * Wang et al. [2017] Pengjun Wang, Tianjun Yang, Tingge Dai, Gencheng Wang, Jie Zhang, Weiwei Chen, and Jianyi Yang.  Design of a flexible-grid 1$\times$ 2 wavelength-selective switch using silicon microring resonators.  _IEEE Photonics Journal_ , 9(6):1–10, 2017.
  * Lira et al. [2009] Hugo LR Lira, Sasikanth Manipatruni, and Michal Lipson.  Broadband hitless silicon electro-optic switch for on-chip optical networks.  _Optics Express_ , 17(25):22271–22280, 2009.
  * Li et al. [2015] Qi Li, Dessislava Nikolova, David M Calhoun, Yang Liu, Ran Ding, Tom Baehr-Jones, Michael Hochberg, and Keren Bergman.  Single microring-based $2\times 2$ silicon photonic crossbar switches.  _IEEE Photonics Technology Letters_ , 27(18):1981–1984, 2015.
  * Velha et al. [2015] Philippe Velha, Isabella Cerutti, Odile Liboiron-Ladouceur, and Nicola Andriolli.  A silicon photonics network-on-chip architecture based on mode and wavelength switching.  In _2015 IEEE 12th International Conference on Group IV Photonics (GFP)_ , pages 120–121. IEEE, 2015.
  * Lee et al. [2009] Benjamin G Lee, Aleksandr Biberman, Nicolás Sherwood-Droz, Carl B Poitras, Michal Lipson, and Keren Bergman.  High-speed $2\times 2$ switch for multiwavelength silicon-photonic networks–on-chip.  _Journal of Lightwave Technology_ , 27(14):2900–2907, 2009.
  * Lee et al. [2008] Benjamin G Lee, Aleksandr Biberman, Nicolás Sherwood-Droz, Carl B Poitras, Michal Lipson, and Keren Bergman.  High-speed $2\times 2$ switch for multi-wavelength message routing in on-chip silicon photonic networks.  In _2008 34th European Conference on Optical Communication_ , pages 1–2. IEEE, 2008.
  * Poon et al. [2008] Andrew W Poon, Fang Xu, and Xianshu Luo.  Cascaded active silicon microresonator array cross-connect circuits for wdm networks-on-chip.  In _Silicon Photonics III_ , volume 6898, page 689812. International Society for Optics and Photonics, 2008.
  * Yu et al. [2013] Runxiang Yu, Stanley Cheung, Yuliang Li, Katsunari Okamoto, Roberto Proietti, Yawei Yin, and SJB Yoo.  A scalable silicon photonic chip-scale optical switch for high performance computing systems.  _Optics Express_ , 21(26):32655–32667, 2013.
  * Beggs et al. [2008] Daryl M Beggs, Thomas P White, Liam O’Faolain, and Thomas F Krauss.  Ultracompact and low-power optical switch based on silicon photonic crystals.  _Optics letters_ , 33(2):147–149, 2008.
  * Zhou et al. [2017] Huanying Zhou, Ciyuan Qiu, Xinhong Jiang, Qingming Zhu, Yu He, Yong Zhang, Yikai Su, and Richard Soref.  Compact, submilliwatt, 2$\times$ 2 silicon thermo-optic switch based on photonic crystal nanobeam cavities.  _Photonics Research_ , 5(2):108–112, 2017.
  * Zhang et al. [2020] Changping Zhang, Ming Zhang, Yiwei Xie, Yaocheng Shi, Rajesh Kumar, Roberto R Panepucci, and Daoxin Dai.  Wavelength-selective 2$\times$ 2 optical switch based on a ge 2 sb 2 te 5-assisted microring.  _Photonics Research_ , 8(7):1171–1176, 2020.
  * Cheng et al. [2019] Qixiang Cheng, Meisam Bahadori, Madeleine Glick, and Keren Bergman.  Scalable space-and-wavelength selective switch architecture using microring resonators.  In _2019 Conference on Lasers and Electro-Optics (CLEO)_ , pages 1–2. IEEE, 2019.
  * Prifti et al. [2018] Kristif Prifti, Netsanet Tessema, Ripalta Stabile, and Nicola Calabretta.  Performance assessment of a nanoseconds and modular photonic integrated wavelength selective switch for optical data centre networks.  In _2018 Photonics in Switching and Computing (PSC)_ , pages 1–3. IEEE, 2018.
  * Konoike et al. [2018] Ryotaro Konoike, Keijiro Suzuki, Takashi Inoue, Takeshi Matsumoto, Teruo Kurahashi, Ayahito Uetake, Kazumasa Takabayashi, Suguru Akiyama, Shigeaki Sekiguchi, Shu Namiki, et al.  Soa-integrated silicon photonics switch and its lossless multistage transmission of high-capacity wdm signals.  _Journal of Lightwave Technology_ , 37(1):123–130, 2018.
  * Geuzebroek et al. [2005] Douwe Geuzebroek, Edwin Klein, Henry Kelderman, Nigel Baker, and Alfred Driessen.  Compact wavelength-selective switch for gigabit filtering in access networks.  _IEEE photonics technology letters_ , 17(2):336–338, 2005.
  * Hwang et al. [2017a] How Yuan Hwang, Jun Su Lee, Tae Joon Seok, Alex Forencich, Hannah R Grant, Dylan Knutson, Niels Quack, Sangyoon Han, Richard S Muller, George C Papen, et al.  Flip chip packaging of digital silicon photonics mems switch for cloud computing and data centre.  _IEEE Photonics Journal_ , 9(3):1–10, 2017a.
  * Dumais et al. [2017] Patrick Dumais, Dominic J Goodwill, Dritan Celo, Jia Jiang, Chunshu Zhang, Fei Zhao, Xin Tu, Chunhui Zhang, Shengyong Yan, Jifang He, et al.  Silicon photonic switch subsystem with 900 monolithically integrated calibration photodiodes and 64-fiber package.  _Journal of Lightwave Technology_ , 36(2):233–238, 2017.
  * Suzuki et al. [2019] Keijiro Suzuki, Ryotaro Konoike, Junichi Hasegawa, Satoshi Suda, Hiroyuki Matsuura, Kazuhiro Ikeda, Shu Namiki, and Hitoshi Kawashima.  Low-insertion-loss and power-efficient 32$\times$ 32 silicon photonics switch with extremely high-$\delta$ silica plc connector.  _Journal of Lightwave Technology_ , 37(1):116–122, 2019.
  * Nakamura et al. [2016] Shigeru Nakamura, Shigeyuki Yanagimachi, Hitoshi Takeshita, Akio Tajima, Tomoyuki Hino, and Kiyoshi Fukuchi.  Optical switches based on silicon photonics for roadm application.  _IEEE Journal of Selected Topics in Quantum Electronics_ , 22(6):185–193, 2016.
  * Lee et al. [2013] Benjamin G Lee, Alexander V Rylyakov, William MJ Green, Solomon Assefa, Christian W Baks, Renato Rimolo-Donadio, Daniel M Kuchta, Marwan H Khater, Tymon Barwicz, Carol Reinholm, et al.  Monolithic silicon integration of scaled photonic switch fabrics, cmos logic, and device driver circuits.  _Journal of Lightwave Technology_ , 32(4):743–751, 2013.
  * Rylyakov et al. [2011] Alexander V Rylyakov, Clint L Schow, Benjamin G Lee, William MJ Green, Solomon Assefa, Fuad E Doany, Min Yang, Joris Van Campenhout, Christopher V Jahnes, Jeffrey A Kash, et al.  Silicon photonic switches hybrid-integrated with cmos drivers.  _IEEE Journal of Solid-State Circuits_ , 47(1):345–354, 2011.
  * Chen et al. [2013] Luis Chen, Avantika Sohdi, John E Bowers, Luke Theogarajan, Jon Roth, and Greg Fish.  Electronic and photonic integrated circuits for fast data center optical circuit switches.  _IEEE Communications Magazine_ , 51(9):53–59, 2013.
  * Hwang et al. [2018] How Yuan Hwang, Jun Su Lee, Johannes Henriksson, Kyungmok Kwon, Tae Joon Seok, Ming C Wu, and Peter O’Brien.  Pluggable silicon photonic mems switch package for data centre.  In _2018 IEEE 20th Electronics Packaging Technology Conference (EPTC)_ , pages 46–49. IEEE, 2018.
  * Atabaki et al. [2018] Amir H Atabaki, Sajjad Moazeni, Fabio Pavanello, Hayk Gevorgyan, Jelena Notaros, Luca Alloatti, Mark T Wade, Chen Sun, Seth A Kruger, Huaiyu Meng, et al.  Integrating photonics with silicon nanoelectronics for the next generation of systems on a chip.  _Nature_ , 556(7701):349–354, 2018.
  * Settaluri et al. [2015] Krishna T. Settaluri, Sen Lin, Sajjad Moazeni, Erman Timurdogan, Chen Sun, Michele Moresco, Zhan Su, Yu-Hsin Chen, Gerald Leake, Douglas LaTulipe, Colin McDonough, Jeremiah Hebding, Douglas Coolbaugh, Michael Watts, and Vladimir Stojanović.  Demonstration of an optical chip-to-chip link in a 3d integrated electronic-photonic platform.  In _ESSCIRC Conference 2015 - 41st European Solid-State Circuits Conference (ESSCIRC)_ , pages 156–159, 2015.  doi:10.1109/ESSCIRC.2015.7313852.
  * Stojanović et al. [2015] V Stojanović, KT Settaluri, S Lin, S Moazeni, E Timurdogan, C Sun, M Moresco, Z Su, YH Chen, G Leake, et al.  High-density 3d electronic-photonic integration.  In _2015 Fourth Berkeley Symposium on Energy Efficient Electronic Systems (E3S)_ , pages 1–2. IEEE, 2015.
  * Marchetti et al. [2017] Riccardo Marchetti, Cosimo Lacava, Ali Khokhar, Xia Chen, Ilaria Cristiani, David J. Richardson, Graham T. Reed, Periklis Petropoulos, and Paolo Minzioni.  High-efficiency grating-couplers: demonstration of a new design strategy.  _Scientific Reports_ , 7(1):16670, Nov 2017.
  * Kang et al. [2020] Shuting Kang, Ru Zhang, Zhenzhong Hao, Di Jia, Feng Gao, Fang Bo, Guoquan Zhang, and Jingjun Xu.  High-efficiency chirped grating couplers on lithium niobate on insulator.  _Opt. Lett._ , 45(24):6651–6654, Dec 2020.
  * Takei et al. [2013] R. Takei, M. Suzuki, E. Omoda, S. Manako, T. Kamei, M. Mori, and Y. Sakakibara.  Silicon knife-edge taper waveguide for ultralow-loss spot-size converter fabricated by photolithography.  _Applied Physics Letters_ , 102(10):101108, 2013\.  doi:10.1063/1.4795308.  URL https://doi.org/10.1063/1.4795308.
  * Dangel et al. [2015] Roger Dangel, Jens Hofrichter, Folkert Horst, Daniel Jubin, Antonio La Porta, Norbert Meier, Ibrahim Murat Soganci, Jonas Weiss, and Bert Jan Offrein.  Polymer waveguides for electro-optical integration in data centers and high-performance computers.  _Opt. Express_ , 23(4):4736–4750, Feb 2015.  doi:10.1364/OE.23.004736.  URL http://www.opticsexpress.org/abstract.cfm?URI=oe-23-4-4736.
  * Dumais et al. [2018] Patrick Dumais, Dominic J. Goodwill, Dritan Celo, Jia Jiang, Chunshu Zhang, Fei Zhao, Xin Tu, Chunhui Zhang, Shengyong Yan, Jifang He, Ming Li, Wanyuan Liu, Yuming Wei, Dongyu Geng, Hamid Mehrvar, and Eric Bernier.  Silicon photonic switch subsystem with 900 monolithically integrated calibration photodiodes and 64-fiber package.  _J. Lightwave Technol._ , 36(2):233–238, Jan 2018\.  URL http://jlt.osa.org/abstract.cfm?URI=jlt-36-2-233.
  * Bogaerts et al. [2018] L. Bogaerts, Z. El-Mekki, S. Van Huylenbroeck, P. Nolmans, N. Pantano, X. Sun, M. Rakowski, D. Velenis, P. Verheyen, S. Balakrishnan, P. De Heyn, B. Snyder, Y. Ban, S. Srinivasan, S. Lardenois, J. De Coster, M. Detalle, P. Absil, A. Miller, M. Pantouvaki, and J. Van Campenhout.  High-speed tsv integration in an active silicon photonics interposer platform.  In _2018 IEEE SOI-3D-Subthreshold Microelectronics Technology Unified Conference (S3S)_ , pages 1–3, 2018.  doi:10.1109/S3S.2018.8640164.
  * Hwang et al. [2017b] How Yuan Hwang, Padraic Morrissey, Jun Su Lee, Peter O’Brien, Johannes Henriksson, Ming C Wu, and Tae Joon Seok.  128$\times$ 128 silicon photonic mems switch package using glass interposer and pitch reducing fibre array.  In _2017 IEEE 19th Electronics Packaging Technology Conference (EPTC)_ , pages 1–4. IEEE, 2017b.
  * Suzuki et al. [2020] Keijiro Suzuki, Ryotaro Konoike, Nobuyuki Yokoyama, Miyoshi Seki, Minoru Ohtsuka, Shigeru Saitoh, Satoshi Suda, Hiroyuki Matsuura, Koji Yamada, Shu Namiki, et al.  Nonduplicate polarization-diversity 32$\times$ 32 silicon photonics switch based on a sin/si double-layer platform.  _Journal of Lightwave Technology_ , 38(2):226–232, 2020.
  * Budd et al. [2015] Russell A Budd, Laurent Schares, Benjamin G Lee, Fuad E Doany, Christian Baks, Daniel M Kuchta, Clint L Schow, and Frank Libsch.  Semiconductor optical amplifier (soa) packaging for scalable and gain-integrated silicon photonic switching platforms.  In _2015 IEEE 65th Electronic Components and Technology Conference (ECTC)_ , pages 1280–1286. IEEE, 2015.
  * Lee and Dupuis [2018] Benjamin G Lee and Nicolas Dupuis.  Silicon photonic switch fabrics: Technology and architecture.  _Journal of Lightwave Technology_ , 37(1):6–20, 2018.
  * Huang et al. [2017] Yishen Huang, Qixiang Cheng, Nathan C Abrams, Ji Zhou, Sébastien Rumley, and Keren Bergman.  Automated calibration and characterization for scalable integrated optical switch fabrics without built-in power monitors.  In _2017 European Conference on Optical Communication (ECOC)_ , pages 1–3. IEEE, 2017.
  * Stojanović et al. [2018] Vladimir Stojanović, Rajeev J Ram, Milos Popović, Sen Lin, Sajjad Moazeni, Mark Wade, Chen Sun, Luca Alloatti, Amir Atabaki, Fabio Pavanello, et al.  Monolithic silicon-photonic platforms in state-of-the-art cmos soi processes.  _Optics express_ , 26(10):13106–13121, 2018.
  * Dupuis [2016] Nicolas Dupuis.  Cmos photonic nanosecond-scale switch fabrics.  In _2016 Optical Fiber Communications Conference and Exhibition (OFC)_ , pages 1–3. IEEE, 2016.
  * Zanetto et al. [2020] Francesco Zanetto, Vittorio Grimaldi, Miltiadis Moralis-Pegios, Stelios Pitris, Konstantinos Fotiadis, Theonitsa Alexoudi, Emanuele Guglielmi, Douglas Oliveira Morais de Aguiar, Peter De Heyn, Yoojin Ban, et al.  Wdm-based silicon photonic multi-socket interconnect architecture with automated wavelength and thermal drift compensation.  _Journal of Lightwave Technology_ , 2020.
  * Khope et al. [2017b] Akhilesh SP Khope, Andrew M Netherton, Takako Hirokawa, Nicolas Volet, Eric J Stanton, Clint Schow, Roger Helkey, Adel AM Saleh, John E Bowers, and Rod C Alferness.  Elastic wdm optoelectronic crossbar switch with on-chip wavelength control.  In _Photonics in Switching_ , pages PTh1D–3. Optical Society of America, 2017b.
  * Aguiar et al. [2018] Douglas Aguiar, Maziyar Milanizadeh, Emanuele Guglielmi, Francesco Zanetto, Ruiqiang Ji, Sujie Zhou, Yanbo Li, Xiaolu Song, Lewei Zhang, Marco Sampietro, et al.  Automatic tuning of microring-based hitless reconfigurable add-drop filters.  In _2018 Optical Fiber Communications Conference and Exposition (OFC)_ , pages 1–3. IEEE, 2018.
  * Jayatilleka et al. [2019] Hasitha Jayatilleka, Hossam Shoman, Lukas Chrostowski, and Sudip Shekhar.  Photoconductive heaters enable control of large-scale silicon photonic ring resonator circuits.  _Optica_ , 6(1):84–91, 2019.
  * Dong et al. [2017] Po Dong, Robert Gatdula, Kwangwoong Kim, Jeffrey H Sinsky, Argishti Melikyan, Young-Kai Chen, Guilhem De Valicourt, and Jeffrey Lee.  Simultaneous wavelength locking of microring modulator array with a single monitoring signal.  _Optics express_ , 25(14):16040–16046, 2017.
  * Gazman et al. [2017] Alexander Gazman, Colm Browning, Ziyi Zhu, Liam R Barry, and Keren Bergman.  Automated thermal stabilization of cascaded silicon photonic ring resonators for reconfigurable wdm applications.  In _2017 European Conference on Optical Communication (ECOC)_ , pages 1–3. IEEE, 2017.
  * Li and Poon [2015] Yu Li and Andrew W Poon.  Active resonance wavelength stabilization for silicon microring resonators with an in-resonator defect-state-absorption-based photodetector.  _Optics express_ , 23(1):360–372, 2015.
  * Grillanda et al. [2014] Stefano Grillanda, Marco Carminati, Francesco Morichetti, Pietro Ciccarella, Andrea Annoni, Giorgio Ferrari, Michael Strain, Marc Sorel, Marco Sampietro, and Andrea Melloni.  Non-invasive monitoring and control in silicon photonics using cmos integrated electronics.  _Optica_ , 1(3):129–136, 2014.
  * Padmaraju et al. [2013] Kishore Padmaraju, Dylan F Logan, Takashi Shiraishi, Jason J Ackert, Andrew P Knights, and Keren Bergman.  Wavelength locking and thermally stabilizing microring resonators using dithering signals.  _Journal of Lightwave Technology_ , 32(3):505–512, 2013.
  * Mak et al. [2015] Jason CC Mak, Wesley D Sacher, Tianyuan Xue, Jared C Mikkelsen, Zheng Yong, and Joyce KS Poon.  Automatic resonance alignment of high-order microring filters.  _IEEE Journal of Quantum Electronics_ , 51(11):1–11, 2015.


# Computing $\varphi(N)$ for an RSA module with a single Quantum Query

Luis Víctor Dieulefait  Departament de Matemàtiques i Informàtica, Universitat
de Barcelona  and  Jorge Urróz  Departamento de Matemáticas e Informática
aplicadas a la Ingeniería Civil y Naval, Universidad Politécnica de Madrid

###### Abstract.

In this paper we give a polynomial time algorithm to compute $\varphi(N)$ for
an RSA module $N$ using as input the order modulo $N$ of a randomly chosen
integer. The algorithm consists only on a computation of a greatest common
divisor, two multiplications and a division. The algorithm works with a
probability of at least $1-\frac{C}{N^{1/2}}$.

##  1\. Introduction

In this paper we give a polynomial time algorithm to compute $\varphi(N)$ for
an RSA module $N$ using as input the order modulo $N$ of a randomly chosen
integer. The algorithm consists only on a computation of a greatest common
divisor, two multiplications and a division (see Theorems 3.9 and 2.1). As it
is well-known, from this value it is easy to factor $N$ by just solving a
quadratic equation. The algorithm works with a probability greater than
$1-\frac{C}{N^{1/2}}$, where $C$ is a constant (in practice it could be $C=16$
for example), and the input can be obtained from a quantum computer by a
single application of Shor’s algorithm (cf. [7] and [8]), assuming that the
output of that algorithm is exactly the order module $N$ of a randomly chosen
integer. This assumption is reasonable since, as explained in [3], the
probability that Shor’s algorithm fails to give the right order is negligible,
under suitable conditions on the parametrization and post-processing of the
quantum algorithm (cf. [3], section 2.1).

In the paper [3], another polynomial time algorithm is given that factors an
integer taking as input the order of a random integer, which is based on a
variation of a method of V. Miller (the same method used by Shor to end his
factorization algorithm, but this time with the extra clever idea of moving
the base in a post-processing process in a classical computer). The algorithm
in [3] can be used to factor arbitrary integers, not only RSA modules, but
even for the case of RSA modules the probability of success is smaller than
$1-\frac{1}{C\log^{2}N}$ (see [3], Theorem 1 111we omit here the term
$-1/{2^{k}}$, where $k$ denotes the number of iterations, since this term is
dominated by the other, for $k$ sufficiently large), thus the probability of
failure is exponentially larger than the one we obtain. Also, our algorithm is
simpler and faster, it consists in giving a formula for $\varphi(N)$ in terms
of the order of a random integer modulo $N$ (involving just one application of
Euclid’s algorithm, two multiplications and a division) which is correct with
very high probability.

The possibility of computing $\varphi(N)$ for an RSA module given the order of
a random integer was also observed in [4] but only for the case of safe
semiprimes (i.e., modules of the form $p\cdot q$ where both $p$ and $q$ are
safe primes, which are by definition primes of the form $2\cdot t+1$ for
another prime $t$), whereas our algorithm works without this restriction.

To finalize this introduction we would like to mention an aditional result
that comes from our method. Concretely, in $1978$, Rivest, Shamir and Adleman
in [6] gave a probabilistic algorithm proving that factoring $N$ is equivalent
to knowing the secret key on the RSA cryptosystem. Namely knowing the public
information $N$ and the public exponent $e$, if one can compute $d$, the
inverse of $e$ modulo $\varphi(N)$, then one can factor $N$ in polynomial time
with high probability. Then May and Coron in [2] improved the result showing a
deterministic algorithm for the reduction of the knowledge of $d$ to factor
$N$. For that, they use an improvement of Coppersmith algorithm (cf. [1])
valid not only for the integer of unknown factorization, but any divisor of
it. Here we show a straightforward proof of this equivalence, in the case that
the exponent $e$ is not too large. Recall that, in practice, the most common
exponent is the constant $3$ or $65537$ .

To simplify the presentation, instead of working with an arbitrary RSA module,
we will restrict to the case of a module $N$ such that the two prime factors
$p$ and $q$ have the same number of bits. This is the case for RSA modules in
practice, in agreement with the Digital Signature Standards fixed by the
National Institute of Standards and Technology (see [5], Appendix A.1.1).
We remark that our results can be easily adapted to cover also the case of
arbitrary RSA modules. In fact, if we assume that both prime factors of $N$
are larger than $N^{1/4}$ then a result similar to Theorem 3.9 can be proved,
just changing $1-\frac{C}{N^{1/2}}$ by $1-\frac{C}{N^{1/4}}$ in the
probability of success. On the other hand, there is no need to consider the
case where one of the prime factors of $N$ is smaller than $N^{1/4}$, since as
it is well-known in that case the method of Coppersmith (see [1]) gives a
polynomial time deterministic algorithm to factor $N$ (with a classical
computer).

The following notation will be used through the whole paper. Given two
integers $a,b$, $(a,b)$ will be their greatest common divisor, while $[a,b]$
will be their least common multiple. It will be useful to recall that

(1.1) $ab=[a,b](a,b)$

Also, $N=pq$ will be the product of the two prime numbers $p$ and $q$ such
that

$\displaystyle p-1$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{r}p_{i}^{a_{i}}P$ (1.2) $\displaystyle q-1$
$\displaystyle=$ $\displaystyle\prod_{i=1}^{r}p_{i}^{b_{i}}Q$

where a prime $l|(p-1,q-1)$ if and only if $l=p_{i}$ for some $1\leq i\leq r$.
We will denote $m_{i}=\min\\{a_{i},b_{i}\\}$ and $M_{i}=\max\\{a_{i},b_{i}\\}$
for $i=1,\dots,r$.

##  2\. Explicit formulas for $\varphi(N)$ and factoring

It is well known that an RSA modulus $N=pq$ can be factored knowing
$\varphi(N)$, simply solving a system of two equations in the unknown $p,q$.
We now prove that, in fact, it is enough to know either a big enough factor of
$\varphi(N)$, or a small enough multiple of $\varphi(N)$.

######  Theorem 2.1.

Let $N=pq$ be the product of two unknown prime numbers $p,q$ of at most $L$
bits, say $p<q\leq 2^{L}$. Suppose we know $D$ such that $DX=(p-1)(q-1)$ and
$D\geq 2^{L+1}$. Then, we can find $p,q$ in polynomial time.

Proof.

$DX=(p-1)(q-1)=N-(p+q)+1,$

so

$\frac{N+1}{D}=X+\frac{p+q}{D},$

where

$0<\frac{p+q}{D}<1,$

so

$\left[\frac{N+1}{D}\right]=X,$

and once we know $X$, then we know $(p-1)(q-1)$ and we solve the system

$\displaystyle N=pq$ $\displaystyle N+1-DX=p+q.$

######  Corollary 2.2.

Let $N=pq$ be the product of two unknown prime numbers $p,q$ of at most $L$
bits, say $p<q\leq 2^{L}$. Suppose we know $D$ such that $DX=(p-1)(q-1)$ and
$D\geq 2^{L+1}$. Then,

$\varphi(N)=\left[\frac{N+1}{D}\right]D.$

######  Theorem 2.3.

Let $N=pq$ be the product of two unknown prime numbers $p,q$ of at most $L$
bits, and suppose $(p-1,q-1)=D>2^{L/2+1}$ is known. Then we can factor $N$ in
polynomial time.

Proof. We know that

$\displaystyle p$ $\displaystyle=$ $\displaystyle 1+R_{p}D$ $\displaystyle q$
$\displaystyle=$ $\displaystyle 1+R_{q}D,$

where $R_{q}+R_{p}<D$ by our conditions. Then since

$N=1+(R_{q}+R_{p})D+R_{q}R_{p}D^{2}$

we get

$R_{p}+R_{q}=\frac{N-1}{D}\pmod{D},$

in particular reducing $N-1/D$ modulo $D$ we get $R_{p}+R_{q}$ and, from there
$p+q=2+R_{p}D+R_{q}D$ and we factor $N$ by solving the system in $p+q$ and
$pq$ as before.

Our next result is about the mentioned relation between factoring and finding
the secret key on an RSA cryptosystem

######  Theorem 2.4.

Let $N=pq$ be the product of two prime numbers of $L$ bits
$2^{L-1}<p<q<2^{L}$, with $(e,\varphi(N)=1$, $e<\frac{\sqrt{N}}{2}$ and
suppose we know its inverse $d$ modulo $\varphi(N)$, namely $1\leq
d\leq\varphi(N)$, such that $ed\equiv 1\pmod{\varphi(N)}$. Then, we can factor
$N$ performing just one multiplication and two divisions.

In fact, we prove a bit more. If we let $M=ed-1=k\varphi(N)$ we have the
following explicit formula of independent interest

######  Corollary 2.5.

Let $N=pq$ the product of two prime numbers of $L$ bits $2^{L-1}<p<q<2^{L}$
$(e,\varphi(N))=1$, $e<\frac{\sqrt{N}}{2}$ and suppose we know its inverse $d$
modulo $\varphi(N)$, namely $1\leq d\leq\varphi(N)$. Then, denoting $M=ed-1$
we have

$\varphi(N)=\frac{M}{\left[\frac{M}{N}\right]+1}.$

###### Proof.

(Of the theorem and the corollary) We know that

$M=ed-1=k\varphi(N)=k(N-(p+q)+1),$

and dividing by $N$ we get

$\frac{M}{N}=k-\frac{k(p+q-1)}{N}.$

but since $M<ed<\frac{\sqrt{N}}{2}\varphi(N)$, we have $k<\frac{\sqrt{N}}{2}$
and hence we get $k(p+q-1)<k(p+q)<N$. The last inequality comes from
maximizing $p+q$ restricted to $pq=N$ and $2^{L-1}<p<q<2^{L}$. Hence,

$0<\frac{k(p+q-1)}{N}<1,$

which gives $k=\left[\frac{M}{N}\right]+1$, and hence the result in the
corollary. Once we know $\varphi(N)$ we can factor $N$ as usual by solving the
system in $p+q$ and $pq$. ∎

##  3\. Factoring and the order of elements modulo $N$.

The results in the previous section are directly related with the problem of
factoring $N$ knowing the order of an element in
$(\mathbb{Z}/N\mathbb{Z})^{*}$, an information that can be obtained from
Shor’s algorithm. Concerning this problem, in [3] it is proved that knowing
the order of a randomly chosen element modulo $N$ one can factor $N$ with
probability smaller than $1-\frac{1}{C\log^{2}N}$ by applying a procedure that
is a variation of the method of Miller proposed by Shor himself in this
context, but with the novel feature that the base is allowed to vary while a
smooth factor is added to the order. On the other hand, in [4] the authors
show that $\varphi(N)$ can be computed for an RSA module from the order of an
element modulo $N$, with high probability, but only for the case of safe
semiprimes. In the remaining of this section, we improve dramatically the
previous results and prove that the knowledge of the order of an element in
$(\mathbb{Z}/N\mathbb{Z})^{*}$ gives the factorization of $N$ with probability
$1-\frac{C}{N^{1/2}}$ assuming that the prime factors of the RSA modulus $N$
have the same length (also, as remarked in the introduction, a variant of this
algorithm also works for arbitrary RSA modules). We shall do this by giving a
short procedure to obtain the value of $\varphi(N)$ given the order of a
random element.

We start by proving the following lemmata:

######  Lemma 3.1.

Let $N$ be an integer, and consider the function defined as
$N(x)=\\#\\{a\in(\mathbb{Z}/N\mathbb{Z})^{*}:\text{ord}_{N}(a)=x\\}$. Then
$N(x)$ is a multiplicative function.

Proof. Suppose $(x_{1},x_{2})=1$ are two coprime integers so that
$N(x_{1})=n_{1}$, and $N(x_{2})=n_{2}$. We will prove that if
$C_{x_{1}}=\\{a_{1},\dots,a_{n_{1}}\\}$ are the elements with order $x_{1}$
and $C_{x_{2}}=\\{b_{1},\dots,b_{n_{2}}\\}$ are the elements with order
$x_{2}$, then $C_{x_{1},x_{2}}=\\{a_{i}b_{j}:1\leq i\leq n_{1},1\leq j\leq
n_{2}\\}$ contains the elements with order $x_{1}x_{2}$.

Suppose ord${}_{N}(a)=x$ and let $(x,y)=1$. Then ord${}_{N}(a^{y})=x$. Indeed
suppose ord${}_{N}(a^{y})=z$. Since $(a^{y})^{x}=(a^{x})^{y}=1\pmod{N}$,
$z|x$. But we know that for some integers $u,v$ we have
$a^{z}=(a^{z})^{uy+vx}=(a^{y})^{zu}(a^{x})^{zv}=1$, so $x|z$ and they are the
same.

Now, we see that every element in $C_{x_{1},x_{2}}$ has order $x_{1}x_{2}$.
First note that $(a_{i}b_{j})^{x_{1}x_{2}}=1\pmod{N}$, so
ord${}_{N}(a_{i}b_{j})|x_{1}x_{2}$ Suppose ord${}_{N}(a_{i}b_{j})=z$ then
$z=z_{1}z_{2}$ where $z_{1}=(z,x_{1})$, and $z_{2}=(z,x_{2})$, but then
$(a_{i}b_{j})^{z_{1}z_{2}}=1\pmod{N}$ so
$(a_{i}^{z_{2}})^{z_{1}}=((b_{j})^{-1})^{z_{1}})^{z_{2}}$, but
ord${}_{N}(a_{i}^{z_{2}})=x_{1}$ and ord${}_{N}(b_{j})^{-1})^{z_{1}}=x_{2}$,
so they can not be equal unless $z_{1}=x_{1}$ and $z_{2}=x_{2}$. On the other
hand $a_{i}b_{j}\neq a_{I}b_{J}$ for any $(i,j)\neq(I,J)$, again for the same
reason since otherwise $\frac{a_{i}}{a_{I}}=\frac{b_{J}}{b_{j}}$ which is
impossible since ord${}_{N}(\frac{a_{i}}{a_{I}})|x_{1}$ and
ord${}_{N}(\frac{b_{J}}{b_{j}})|x_{2}$.

So we have proved that the $n_{1}n_{2}$ elements in $C_{x_{1},x_{2}}$ are
indeed distincts and have order $x_{1}x_{2}$. Now we need to prove that there
are no more. Suppose $w\in(\mathbb{Z}/N\mathbb{Z})^{*}$ has
ord${}_{N}(w)=x_{1}x_{2}$. We will prove that $w$ is the product of two
elements $w=a_{i}b_{j}$ for $a_{i}\in C_{x_{1}}$ and $b_{j}\in C_{x_{2}}$. But
for some integers $u,v$ such that $(ux_{1},vx_{2})=1$ we have

$w=w^{ux_{1}+vx_{2}}=w^{ux_{1}}w^{vx_{2}}$

But if ord${}_{N}(w^{ux_{1}})=z$ then $z|x_{2}$ and $(u,z)=1$ so
ord${}_{N}(w^{x_{1}})=z$ and hence $z=x_{2}$ in the same way we prove that
ord${}_{N}(w^{vx_{1}})=x_{1}$ finishing the proof of the lemma.

######  Lemma 3.2.

Let $N=pq$ the product of two primes, $x|[p-1,q-1]$ and let
$N(x)=\\#\\{a\in(\mathbb{Z}/N\mathbb{Z})^{*}:\text{ord}_{N}(a)=x\\}$. Then

(3.1) $N(x)=\varphi(x)(x,N-1)\sum_{\begin{subarray}{c}d|(x,N-1)\\\
\left(d,\frac{x}{(x,N-1)}\right)=1\end{subarray}}\frac{\mu^{2}(d)}{d}$

Proof. We will denote $x$ as $x=\prod_{1\leq i\leq
r}p_{i}^{\alpha_{i}}P_{x}Q_{x}$ where $P_{x}|P$ and $Q_{x}|Q$, with the
notation in (1). Since $N(x)$ is multiplicative, we just need to compute
$N(l^{a})$ for $l$ a prime number. Now if $l\nmid(p-1,q-1)$ and $l|p-1$, then
if $e_{p}|(p-1)$ and $e_{q}|q-1$ are such that $[e_{p},e_{q}]=l^{a}$, then
$e_{p}=l^{a}$, $e_{q}=1$ and we have $N(l^{a})=\varphi(l^{a})$. If $l=p_{i}$
for some $1\leq i\leq r$, then we have to distinguish two cases.

Case 1. Suppose $\alpha_{i}\leq m_{i}$ Then, if $e_{p}|(p-1)$ and $e_{q}|q-1$
are such that $[e_{p},e_{q}]=p_{i}^{\alpha_{i}}$, then either
$e_{p}=p_{i}^{\alpha_{i}}$ and $e_{q}=p_{i}^{c_{i}}$ for some $0\leq
c_{i}\leq\alpha_{i}$ or $e_{q}=p_{i}^{\alpha_{i}}$ and $e_{p}=p_{i}^{c_{i}}$
for some $0\leq c_{i}\leq\alpha_{i}$. And, since we are counting
$p_{i}^{\alpha_{i}}$ twice, we get in this case

$\displaystyle 2\sum_{0\leq
c_{i}\leq\alpha_{i}}\varphi(p_{i}^{\alpha_{i}})\varphi(p_{i}^{c_{i}})-\varphi(p_{i}^{\alpha_{i}})^{2}=2p_{i}^{\alpha_{i}}\varphi(p_{i}^{\alpha_{i}})-\varphi(p_{i}^{\alpha_{i}})^{2}$
$\displaystyle=\varphi(p_{i}^{\alpha_{i}})(2p_{i}^{\alpha_{i}}-p_{i}^{\alpha_{i}}+p_{i}^{\alpha_{i}-1})=\varphi(p_{i}^{\alpha_{i}})p_{i}^{\alpha_{i}}\left(1+\frac{1}{p_{i}}\right)$

Case 2. Suppose $m_{i}<\alpha_{i}$ and let $a_{i}=M_{i}$. Then, if
$e_{p}|(p-1)$ and $e_{q}|q-1$ are such that
$[e_{p},e_{q}]=p_{i}^{\alpha_{i}}$, then $e_{p}=p_{i}^{\alpha_{i}}$ while
$e_{q}=p_{i}^{c_{i}}$ for some $0\leq c_{i}\leq m_{i}$, so in this case

$N(p_{i}^{\alpha_{i}})=\varphi(p_{i}^{\alpha_{i}})\sum_{0\leq c_{i}\leq
m_{i}}\varphi(p_{i}^{c_{i}})=\varphi(p_{i}^{\alpha_{i}})p_{i}^{m_{i}}$

Putting all together we get

$\displaystyle N(x)$ $\displaystyle=$
$\displaystyle\varphi(P_{x}Q_{x})\prod_{\begin{subarray}{c}\alpha_{i}\leq
m_{i}\end{subarray}}\varphi(p_{i}^{\alpha_{i}})p_{i}^{\alpha_{i}}\left(1+\frac{1}{p_{i}}\right)\prod_{\begin{subarray}{c}\alpha_{i}>m_{i}\end{subarray}}\varphi(p_{i}^{\alpha_{i}})p_{i}^{m_{i}}$
$\displaystyle=$
$\displaystyle\varphi(P_{x}Q_{x})(x,N-1)\varphi(\frac{x}{P_{x}Q_{x}})\prod_{\alpha_{i}\leq
m_{i}}\left(1+\frac{1}{p_{i}}\right)$ $\displaystyle=$
$\displaystyle\varphi(x)(x,N-1)\sum_{\begin{subarray}{c}d|(x,N-1)\\\
\left(d,\frac{x}{(x,N-1)}\right)=1\end{subarray}}\frac{\mu^{2}(d)}{d}.$

######  Lemma 3.3.

Let $N=pq$ be the product of two prime numbers $p$ and $q$ and let
$D|[p-1,q-1]$. Then, $(D,p-1,q-1)=(D,N-1)$.

Proof. First we note that for any prime $l$ so that $l^{a}|[p-1,q-1]$ then
either $l^{a}|p-1$ or $l^{a}|q-1$ and hence, noting that $N-1=(p-1)q+(q-1)$,
if $l^{a}|([p-1,q-1],N-1)$, then $l^{a}|(p-1,q-1)$ and hence we deduce
$(D,N-1)|(D,p-1,q-1)$. On the other hand $(D,p-1,q-1)|(D,N-1)$, so they must
be equal.

######  Corollary 3.4.

If $D|[p-1,q-1]$ then $D(D,N-1)|\varphi(N)$.

Proof. Using the previous Lemma we see that

$\displaystyle D(D,N-1)$ $\displaystyle=$ $\displaystyle D(D,(p-1,q-1))$
$\displaystyle=$ $\displaystyle[D,(D,(p-1,q-1))](D,(D,(p-1,q-1))$
$\displaystyle=$ $\displaystyle D(D,(p-1,q-1))$

and since $D|[p-1,q-1]$ and $(D,(p-1,q-1))|(p-1,q-1)$ we get

$D(D,N-1)|[p-1,q-1](p-1,q-1)=(p-1)(q-1)=\varphi(N).$

######  Corollary 3.5.

Let $p-1=\prod_{i=1}^{r}p_{i}^{a_{i}}P$, $q-1=\prod_{i=1}^{r}p_{i}^{b_{i}}Q$
where a prime $l|(p-1,q-1)$ if and only if $l=p_{i}$ for some $1\leq i\leq r$.
Suppose $D|[p-1,q-1]$ and consider the sequence $D_{1}=D$,
$D_{j+1}=\frac{D_{j}}{(D_{j},N-1)}$. Then for some $j_{0}$ we have
$D_{j}=D_{j_{0}}$ for all $j\geq j_{0}$ and $D_{j_{0}}|PQ$.

Proof. Let $m_{i}=\min\\{a_{i},b_{i}\\}$ and suppose
$p_{i}^{\alpha_{i}}||D_{j}$ for $1\leq i\leq r$. Then if $\alpha_{i}\leq
m_{i}$ then $p_{i}^{\alpha_{i}}||(D_{j},N-1)$ and $p_{i}\nmid D_{j+1}$. If
$\alpha_{i}>m_{i}$ then $p_{i}^{m_{i}}||(D_{j},N-1)$ and
$p_{i}^{\alpha_{i}-m_{i}}||D_{j+1}$ and iterating we get the result.

######  Remark 3.6.

Observe that if
$D=\prod_{i=1}^{r}p_{i}^{\alpha_{i}}P_{D}Q_{D}=C_{D}P_{D}Q_{D}$, where
$P_{D}|P$ and $Q_{D}|Q$, then $D_{j_{0}}=P_{D}Q_{D}$ and
$\frac{D}{D_{j_{0}}}=\prod_{i=1}^{r}p_{i}^{\alpha_{i}}$.

One can use the previous remark to give a result that allows factorization
directly in terms of $(p-1,q-1)$, improving Theorem 2.3 in some cases.

######  Theorem 3.7.

Let $N=pq$ where $p$ and $q$ and $D=C_{D}P_{D}Q_{D}=C_{D}D_{j_{0}}$ are as in
Corollary 3.5 and denote $F=(C_{D},N-1)$. Then, if

$D_{j_{0}}>\frac{(p-1+q-1)}{F^{2}},$

we can factor $N$ in polynomial time.

Proof. The proof is the same as in Theorem 2.1. Note that

$N-1-(p-1+q-1)=\varphi(N)=[p-1,q-1](p-1,q-1)$

and since $D|[p-1,q-1]$, and $F|(p-1,q-1)$, we have

$N-1-(p-1+q-1)=DFX,$

for some integer $X$. Dividing by $DF$ we get

$\frac{N-1}{DF}=X+\frac{p-1+q-1}{DF},$

but, by hypothesis,

$DF=D_{j_{0}}C_{D}F\geq D_{j_{0}}F^{2}>(p-1+q-1)$

and, in particular $X=\left[\frac{N-1}{DF}\right]$. Once we have $X$, we have
$\varphi(N)$ and we can factor $N$.

We are now ready to prove the main theorem. We need the following:

######  Definition 3.8.

Let $O$ be the random oracle defined in the following way: each time we call
$O$, it selects uniformly at random a pair from the set
$C=\\{(a,d):a\in(\mathbb{Z}/N\mathbb{Z})^{*},d|[p-1,q-1],\text{ord}_{N}(a)=d\\}$
, and returns $d$.

######  Theorem 3.9.

Let $N=pq$ the product of two unknown primes of $L$ bits $2^{L-1}<p<q<2^{L}$
We can factor $N$ in polynomial time with probability bigger than
$1-\frac{C}{N^{1/2}}$ with just one call to $O$.

Proof Let $x$ be the integer returned by $O$. Note that if we denote $P(x)$
the probability that the oracle returns $x$, then since the oracle selects $x$
and $d$ uniformly at random, we have $P(x)=\frac{N(x)}{\varphi(N)}$.

If $x\geq 4N^{\frac{1}{2}}$, recalling that $x|[p-1,q-1]|\varphi(N)$, we just
apply Theorem 2.1 to get the factorization. So we suppose $x<4N^{1/2}$. If ,
moreover, $N(x)<4N^{1/2}$, $O$ will select $x$ with probability smaller than
$\frac{16}{N^{1/2}}$, by noticing that

$\varphi(N)=N-(p+q)+1\geq N-4\sqrt{N}>CN.$

For example if $N>30$, we could take $C=16$, since then we have
$N-4\sqrt{N}>N/4$.

Otherwise we may assume $N(x)\geq 4\sqrt{N}$. In this case we consider the
integer $x(x,N-1)$ wich is a divisor of $\varphi(N)$ by Corollary 3.4, and by
Lemma 3.2,

$\displaystyle 4\sqrt{N}$ $\displaystyle\leq$ $\displaystyle
N(x)=\varphi(x)(x,N-1)\sum_{\begin{subarray}{c}d|(x,N-1)\\\
\left(d,\frac{x}{(x,N-1)}\right)=1\end{subarray}}\frac{\mu^{2}(d)}{d}$
$\displaystyle\leq$ $\displaystyle
x(x,N-1)\prod_{p|(x,N-1)}\left(1-\frac{1}{p^{2}}\right)<x(x,N-1),$

where we have used

$\varphi(x)=x\prod_{p|x}\left(1-\frac{1}{p}\right)\leq
x\prod_{p|(x,N-1)}\left(1-\frac{1}{p}\right),$

and

$\sum_{\begin{subarray}{c}d|(x,N-1)\\\
\left(d,\frac{x}{(x,N-1)}\right)=1\end{subarray}}\frac{\mu^{2}(d)}{d}\leq\sum_{d|(x,N-1)}\frac{\mu^{2}(d)}{d}=\prod_{p|(x,N-1)}\left(1+\frac{1}{p}\right).$

So, we can apply Theorem 2.1 with $D=x(x,N-1)$ to get the factorization.

## References

  * [1] D. Coppersmith.  Small solutions to polynomial equations, and low exponent rsa vulnerabilities.  J. Cryptology, 10(233-266), 1997.
  * [2] J.-S. Coron and A. May.  Deterministic polynomial time equivalence of computing the rsa secret key and factoring.  Journal of Cryptology, (2004/208), 2004.
  * [3] M Ekera.  On completely factoring any integer efficiently in a single run of an order finding algorithm.  Quantum Inf. Process, 20(205), 2021.
  * [4] F. Grosshans, T. Lawson, Morain F., and B Smith.  Factoring safe semiprimes with a single quantum query,.  preprint at https://arxiv.org/pdf/1511.04385.
  * [5] National Institute of Standards and Technology.  Digital signature standards.  FIPS, 186-5, 2023.
  * [6] R. Rivest, A. Shamir, and L. Adleman.  A method for obtaining digital signatures and public-key cryptosystems.  Communications of the ACM, 21(2):120–126, 1978.
  * [7] P. W. Shor.  Algorithms for quantum computation: Discrete logarithms and factoring.  SFCS, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994.
  * [8] P. W Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM Journal on Computing, 26(5):1484–1509, 1997.